|
在前两期的文章中我们介绍了图灵机和λ算子对计算机发展的影响。图灵机和λ算子之间的区别是：图灵机强调的是过程，而λ算子强调的是结果。基于这两种不同，也因此演化出了当今的两大类编程语言：命令式编程和函数式编程。 这一期我们将更深入的走进图灵机和λ算子的原理，看看它们是如何做最基本的计算并以此为基础构建出现代计算机的。距上一次的计算机系列更新已经有一段时间了，在这里笔者向大家表示歉意，其主要原因是这篇文章的背后大量的数学推理，而笔者要做的便是尽量掩盖数学的复杂性并用最简单的语言阐述其原理。希望有兴趣的读者可以在这篇文章的基础上做进一步的研究。 为了描述的简洁，本文用基础乘法运算（2 x 3）为例来描述图灵机和λ算子的运算方式。之所以用乘法为例，是因为乘法运算中包含了重复的加法运算，而减法和除法运算可分别转化成加法（加一个相反数）和乘法运算（乘以一个倒数）。在了解了乘法运算原理的基础上，我们可以同理得出另外三则运算的原理。 我们先来回顾一下图灵机的结构。在之前的文章中我们讲到，图灵机由一个无限长的纸带（TAPE），读写头（HEAD），一套控制读写头移动规则的规则表（TABLE）和一个状态寄存器（REGISTER）组成，如图一所示。 △ 图一：图灵机结构 纸带被分为无限个格子（起始格由S表示），可记录任何字母，二进制数字（0,1）以及空白（由B表示）。每个格子里代表了图灵机的输入和输出信息而空白则表示没有任何信息。上方箭头为读写头，表示当前读写（输入输出）的位置。读写头可向左右移动，每次移动一格。其移动方向由当下读写头所指的输入和规则表决定（规则表其实就是当时控制计算机的程序）。读写头首先记录下当下位置的状态（q）并存入状态寄存器，然后根据当下输入对比程序中的要求进行左右移动或停留在当下位置，最后根据程序输出字母或数字，修改新的位置的数字或字母。每次工作图灵机的读写头都会从起始位置开始，由规则表和输入控制其移动到不同位置，并最终在程序结束时停留在空白格里。 接下来我们以 2 x 3 为例，来看图灵机如何做运算。首先图灵机会以两个1表示数字2，用三个1表示数字3，并将他们写在纸带上，由数字0表示结束，如图二所示。 △ 图二：基础乘法中的图灵机设置。 S表示开始位置，前两个1表示被乘数2并由0表示结束，接着的三个1表示乘数3并由0表示结束。 B表示空白格，而最终所得出的结果会在空白各种表示出来。我们知道计算结果会是6，所以我们预期的结果应该是有6个空白格被写上1. 那么图灵机是怎么做到的呢? 其最终的思想是将乘数（三个1）复制两次到空白格上。我们一步一步来看：
△ 图三：基础乘法中的图灵机的中间状态。 由图三我们可以看出，在结束以上六个步骤之后，我们成功地将乘数中的三个1复制到了三个空白格中。那么接下来我们需要做的就是将以上步骤再做一次。首先我们需要在图3的基础上，将读写头向左移动（每次一格子）直到遇到B。需要注意的是，在该过程中，如果遇到Y，读写头会将Y改写成1。此时读写头会在起始位置S后面的空白格B上，图三中的所有Y也将被改写成为1。在此基础上，我们可以再次重复做之前提到的六个步骤，并得到最终状态如图四所示。 △ 图四：基础乘法中的图灵机的最终状态。 经过一系列的读写头移动及对纸带的读写，图灵机成功的将乘数（三个1）复制了两次，完成了 2 x 3 的计算。上述的整个运行步骤可以被看作是写在图灵机上的程序，并存在规则表中。如果用有限状态机来表示规则表的内容，上述的整个运行步骤可由图五表示。其中每一个q表示一个状态，L和R表示读写头向左或向右移动一格， A/B 表示读写头将格子中的A改写为B。例如，1/B,R 表示读写头将格子中的1改写成为B，并向右移动一格。Accept 表示程序完成时读写头的状态。 △ 图五：基础乘法中的图灵机规则表。 至此我们介绍了图灵机的乘法运算原理，所有其他运算也都可以在此基础上如法炮制，笔者在这里不做赘述。最后，笔者用一小段的篇幅介绍一下与图灵机等价的λ算子是如何做四则运算的。因所涉及的数学较多，笔者在此仅介绍λ算子中的运算原理。 在λ算子中，我们通过定义两个函数，零（zero）和后趋势（successor）为基础，从而推导出其他运算方式的λ算子表达式。如图六所示，我们通过定义零和后驱得到加法的λ算子表达式，并通过加法的λ算子表达式进而推导出乘法的λ算子表达式。任意两个数字可以赋值于λ算子表达式上，并通过alpha-变换规则和beta-规约规则得到运算结果。与图灵机不同的是，λ算子作为纯数学表达在运算时并没有机器状态改变的这一概念。也正是因为这一特征，λ算子与图灵机共同构造了计算机中的“计算”与“机”的概念。 △ 图六：加法与乘法运算的λ算子表达式。 下期预告：至此，我们完成了对计算机两大基石——图灵机与λ算子的讨论。在此基础上，计算机领域发展出了语言和体系结构两个大的分支，并在这两个分支的基础上发展出了包括网络，算法，人工智能等更为上层的分支。计算机的计算速度也是日新月异。在一一介绍这些分支之前，我们将在下期探讨一这样个问题，计算机的极限究竟在哪里？欢迎大家在留言区对这个问题的各个方面进行讨论。 |
|
|
