算法、图灵机或者普适图灵机究竟是什么呢？为何这些概念在可以构成“思维仪器”的东西的现代观点中占有如此核心的地位呢？是否在原则上存在一个算法可达到的绝对极限呢？为了充分地讨论这些问题，我们必须比较细致地考察算法和图灵机的观念。我在下面的各种讨论中，有时将要用到一些数学表达式。我注意到有些读者排斥这类东西，或者觉得它们吓人。如果你是这种读者，那么我请你原谅，并请你按照我在“敬启读者”中的建议。其实，这里论证所需的数学知识并不超过小学水平，但要仔细地弄通它们，则需要一些认真的思考。事实上，大部分描述是十分显明的，只要细心地跟随就能很好地理解。
但是，如果人们只是为了稍微领略其风味而取其精华，也能有很大的收益。
另一方面，如果你是一位专家，我还要请你原谅。我猜想，它仍然值得你花一段时间把我所说的看过一遍，并且可能会有一两件东西引起你的兴趣。
“算法”这个词来自于九世纪波斯数学家阿布?雅发?穆罕默德?依伯恩?缪莎?阿勒――霍瓦里松，他在公元825年左右写了一本影响深远的《代数对话录》。“算法”这个字现在之所以被拼写成“algorithm”，而不是早先的更精确的“algorism”，似乎是由于和“算术” (arithmetic)相关联所引起的。（还值得指出的是，“代数”(algebra)这个词来源于该书的题目的阿拉伯字“al jabr”。)然而，比阿勒――霍瓦里松的书早很多就知道了算法的实例。现在被称作欧几里德算法的找两个数最大公约数的步骤是在古希腊（公元前300年左右）即有记载的一个最熟知的例子。让我们看看这是如何进行的。随意取两个特定的数，譬如讲1365和3654。所谓的最大公约数是可以同时整除这两个数的最大的整数。在应用欧几里德算法时，我们让这两数中的一个被另一个除并取余数，在3654中取出1365的两倍，其余数为924（=3654-2730）。我们现在用此余数即924以及我们刚用的除数即1365去取代原先的两个数。我们用这一对新的数重复上述步骤，用924去除1365，余数为441。这又得到新的一对441和924，我们用441除924，得到余数42（=924-882），等等，直到能够被整除为止。我们把这一切如下列出：
3654÷1365 给出余数9241365÷924 给出余数441924÷441 给出余数42441÷42 给出余数2142÷21 给出余数0。
我们最后用于做除数的21即是所需要的最大公约数。欧几里德算法本身是我们寻找这一因子的系统步骤。我们刚才把这一步骤应用于特殊的一对数，但是这步骤本身可被十分广泛地应用于任意大小的数。对于非常大的数，要花很长时间来执行该步骤，数字越大则所花的时间越长。但在任何特定的情形下，该步骤最后会终结，并在有限的步骤内得到一个确定的答复。每一步骤所要进行的运算都是非常明了的。此外，尽管它可应用到大小没有限制的自然数上去的这个事实，但是可以用有限的术语来描述整个过程。（“自然数”简单地就是通常的非负1整数0，1，2，3，4，5，6，7，8，9，10，11……）。的确很容易建立一个（有限的）描述欧几里德算法全部逻辑运算的“流程图”。
应该提到，我们在这里隐含地假定，已经“知道”如何实行从两个任意自然数A和B的除法中得到余数的必须的基本运算，所以这一步骤还未完全被分解成最基本的部分。那种运算又是算法的，是用我们在小学学到的除法的非常熟悉的步骤来进行的。在实际上，这个步骤比欧几里德的其他部分更复杂不少，但是可以再为它建立一个流程图。其复杂性主要起源于这个事实，即我们是（假定）对自然数用标准的“十进位”记号，这样子我们需要列出全部的乘法表和忧虑移位等等。如果我们简单地用一连串某种n个记号来代表数n，例如……代表五，那么可从非常初等的算法运算看到余数的形成。为了得到当A被B除时的余数，可以简单地从代表A的记号中不断取走代表B的符号串，直到最后余下的记号不够再进行这种运算为止。最后剩下的符号串提供了所需的答案。例如，为了得到十七被五除的余数，我们可以简单地从……………不断地取走五的序列……正如下面所示：
………………
……………
…………．．由于我们不能再继续这种运算，所以很清楚，其答案是二。
用这种连续减法找到除法余数的流程图可由下图给出：
为了使欧几里德算法的全部流程图完整，我们把上面形成余数的流程图代入到原先流程图的中右部的盒子中去。这种把一个算法向另一个代入是一种普遍的编电脑程序的步骤。上述寻求余数的算法是一道子程序的例子，也就是说，它是由主程序当作它的运算的一部分（通常是预先知道的）召来使用的算法。
当然，把数n简单地用n个斑点来表示，在涉及到大数时效率非常低，这就是为什么我们通常用更紧凑的诸如标准的（十进位）系统的原因。然而，我们在这里并不特别关心运算或记号的效率。我们所关心的是运算在原则上是否可被算法地实行的问题。如果我们用一种数的记号是算法的东西，则用另一种记号也是算法的。两种情况中只有在细节上和复杂性上有差别。欧几里德算法只是在整个数学中可找到的大量的经典算法步骤之一。
尽管算法的这一特殊例子的历史渊源， 一般算法概念的准确表达只从本世纪起才有记载，也许这是令人印象深刻的。事实上，这一概念的各种不同描述都是在本世纪三十年代给出的。称作图灵机的概念是最直接的、最有说服力的、也是历史上最重要的。相当仔细地考查这些“机器”将是很适当的。
关于图灵 “机” 有一件事必须记在心里， 就是说它是一段 “抽象数学”，而不是一个物理对象。这一概念是由英国数学家、非凡的破码专家兼电脑科学的开山鼻祖阿伦?图灵在1935―1936年间提出的（图灵1937）。其目的是为了解决称为判决问题的一个范围广阔的问题。它是由伟大的德国数学家大卫?希尔伯特部分地于1900年巴黎国际数学家会议上（“希尔伯特第十问题”），更完整地于1928年玻罗那国际会议上提出的。希尔伯特不多不少地要求解决数学问题的一般算法步骤，或者不如讲，是否在原则上存在这样步骤的问题。希尔伯特还有一个要把数学置于无懈可击的坚固基础上的宏伟规划，其中公理和步骤法则一旦定下就不能变。但是在图灵完成其伟大的工作之际，这个规划已经遭受到由奥地利才气焕发的逻辑学家库尔特?哥德尔在1931年证明的令人吃惊的定理的粉碎性打击。我们将在
