论图灵的可计算思想

胡 嵩

(华中师范大学 马克思主义学院，武汉 430070)



论图灵的可计算思想

胡 嵩

(华中师范大学 马克思主义学院，武汉 430070)

图灵的可计算思想有着深刻的思想渊源，莱布尼兹、弗雷格和哥德尔对于人工语言研究的发展皆对图灵的可计算思想有影响。图灵在《论可计算数在判决性问题中的应用》中提到图灵机和通用计算机两个抽象机器，并描述了两种机器的基本结构以及运行方式，其中，通用计算机是现代计算机的原型。图灵的可计算思想从根本上影响了冯·诺依曼，并使得冯·诺依曼建造出人类第一台计算机。图灵对于现代计算机以及机器思维方面的发展所做出的贡献是无法取代的。

可计算思想；图灵机；通用计算机；现代计算机；机器思维

图灵多数情况是因其论文被人提及，而他的名字与历史上3个大型计算机项目是密切相关的。第一个是巨人(Colossus)。第二次世界大战时，图灵打破了恩尼格码(Enigma，大西洋之战的一个决定性因素)的神话，他在布莱切利公园设计出了“bombe(一种高速破译德军密码的机器)”，从而破译出恩尼格码产生的大量军事密码。图灵与他同事的工作使得二战在欧洲战场的时间缩短至少两年[1]。二战结束后，图灵被英国的国家物理实验室(the National Physical Laboratory)招募，他不仅设计了电子数字计算机(通用图灵机的现实版本)，并对其发展做出了不可磨灭的贡献，他的设计(the Automatic Computing Engine的设计)相比于其他学者构建的更为先进。在等待工程师建造ACE的同时，图灵和他的团队开创了计算机程序科学的研究，为将要建造出的计算机写了大量复杂的数学程序。随后一年，西方国家的几个团队开始着手在硬件方面做出一台通用计算机。曼彻斯特大学的纽曼电子计算机实验室率先做出一台能够运行的电子存储计算机，这台机器叫做“Manchester Baby”。随后，图灵在纽曼的力邀之下，参与了纽曼的计算机项目，并于1948年6月21日在该台机器上运行了第一个程序。不久之后，图灵为“Manchester Baby”设计出了输入/输出设备(I/O)和扩大化的机器的程序系统，称为“Manchester Mark Ⅰ”。

一、图灵可计算思想的渊源

阿兰·麦西森·图灵生于1912年6月23日，卒于1954年6月7日。图灵一生所致力的研究对于逻辑学、数学、生物学、哲学、密码分析和随后形成的计算机科学、认知科学、人工智能和人工生命领域都有巨大贡献。图灵的可计算思想受莱布尼兹和弗雷格的影响，并在很大程度上受到哥德尔的启发。

莱布尼兹是现代形式逻辑的构设者和初步奠基者,他曾致力于把人的理性部分地还原为计算，并且用机器来执行这些计算。莱布尼兹认为他的宏伟计划主要有3步：首先，创造一套能够涵盖所有人类知识的纲要或百科全书；其次，选择其背后的关键基础概念，为每个概念提供合适的符号，并证明为它们提供合适符号的可行性；最后，制定合适的演绎规则来操作这些被定义的符号，演绎规则即为莱布尼兹所说的“推理演算”。

弗雷格是莱布尼兹计划的继承者，他想要找到某种不用逻辑来发展逻辑的方法，他的方法是用精确的语法规则或句法规则，把概念文字发展成一种人工语言，而他的方法直接促使图灵构想出可计算思想。由于弗雷格试图找到一个可以包含数学实践中全部演绎推理的逻辑系统，并想以其逻辑为基础把代数构造出来，所以他引入了一些自己的特殊符号来表示逻辑关系。他发现那些连接命题的关系也可用于分析命题的结构，于是把这些关系作为他的逻辑基础，第一次用精确的句法构造了形式语言。这一思想不仅成为后来现代逻辑的基础，而且使得逻辑推理能够转化为机械演算的推理规则。与此同时，弗雷格的逻辑也给人们提出了一个需要研究的问题，即能否找到一种计算方法，能够说明在他的逻辑中某一推理是否正确[2]，这个问题被称为希尔伯特的“判定问题”，即：“对于一个一阶逻辑的公式，如何找到一种方法，可以在定义明确的有限步骤内判定这个公式是否是有效的。”[2]

哥德尔对于这个问题的解决也给图灵的可计算思想带来了影响，当他在思考希尔伯特的“判定问题”时，发现数学系统中始终存在一些无法被证明是否成立的命题。1931年，哥德尔发表了论文，提出了不完全性定理，证明了希尔伯特问题是不可判定的。在哥德尔的论文发表之后，人们已经知道了希尔伯特所谓的算法是不存在的，但图灵的一篇文章从另一个角度证明了不完全定理的正确性。

图灵在1935年春得知了希尔伯特的“判定问题”之后，开始思考怎样才能证明这样的算法是不存在的，而后在1936年发表了他重要的论文《论可计算数在判决性问题中的应用》。在这篇论文中他给出了一个新的数学推理分析，“判定问题”难以被一台通用计算机所解决(即使有无限的时间和存储)，图灵描绘的这种抽象计算机(现在被称为通用图灵机)被认为是现代计算机的原型。

二、图灵的可计算思想的主要观点

《论可计算数在判决性问题中的应用》[3]首次于1936年在《伦敦数学学会会刊》(ProceedingsoftheLondonMathematicalSociety)上出现。图灵开创了计算机理论并推动了其发展，他在文中介绍了著名的通用计算机(在发表后就被美国逻辑学家丘奇称为“图灵机”[4])。这篇文章被看作是现代计算机科学的元论文。在20世纪30年代，它为电子存储程序数字计算机的发展贡献了极其重要的思想，而且它是现代计算机基本原理的来源。这个控制机器运作的思想是以存储在计算机内存中的编码命令构成的程序来实现的。

首先，图灵描述了图灵机的构成。图灵指出，一台图灵机是由一个扫描仪和一个能够在扫描仪中来回移动的无限存储纸带所构成。纸带被分为若干个区域(格)，每个区域上是空白的或只有一个符号0或1(或是有限字母表上的符号)，扫描仪在一个时刻只能扫描纸带上的一个区域(称为被扫描区域)。扫描仪有擦除扫描区域的符号、在扫描区域写上符号、使纸带向左或向右移动的机制。除了这些操作之外，扫描仪还能够改变图灵所称为的“m-格局(m-configuration)”，在现代图灵机的术语中，通常用“状态(state)”来代替“m-格局”。扫描仪中有能够接受各种不同状态的装置，而且扫描仪能够在必要的时候改变这个装置的状态，这个装置的工作原理类似于一个简单的存储器。

这样的操作(擦除、写、移动和改变状态)是图灵机的基本操作(原子操作)。操作的复杂性就在于将大量的基本操作连接起来。适用于商业的计算机是通过硬接线来完成最基本的操作，相比于图灵机这类机器更为复杂。然而明显的是，虽然图灵机是很简单的，但它可以计算任何商用计算机能够计算的东西。事实上，因为图灵机是抽象的机器，有无限的存储，因此在现实中找不到一台计算能力可以与之相匹配的计算机。

其次，图灵描述了图灵机的运行程序。图灵所描述的计算机以一条空白纸带开始工作，这个纸带是无限长的，问题就在于启动机器之后，扫描仪处于纸带上的任何一个区域，从开始的地方向右运行，若给机器一个动力，扫描仪是否就会在纸带上写下所期望的数字数列。为了做这项工作，这个机器需要处于某种“状态”。当机器开始工作时，它处于初始状态，在一个扫描区域的操作完成之后，机器处于结束状态，同时这个结束状态是下一个扫描区域的初始状态。机器要进行的操作是由规则表所控制的，每一个指令规则表是由若干行格局(Configuration)和行为(Behaviour)所组成的，而格局可分为m-格局(m-configuration)和符号(symbol)，行为可分为操作(operations)和最终m-格局(final m-configuration)。这样一行规则表由4个要素组成：(1)m-格局是机器的初始状态；(2)符号是扫描仪在所停留的区域扫描到的符号；(3)操作是扫描仪在确定了扫描区域的初始状态以及在扫描区域扫描到的符号之后，要进行的操作(若有符号决定是否擦除，若无符号则决定是否在扫描区域打印符号，然后扫描仪向左向右或停止)；(4)最终m-格局是机器的结束状态。一台机器在某个指令规则表的指示下运行，也许会无止境地运行下去，同样也可能在运行一段时间之后停止下来，这是取决于规则表的设计者是如何去设计这个规则表的。

在最后的分析中，一个计算机程序仅仅是一长串符号流或列，即为符号的组合体编码命令。每一行的规则表命令可以再次改写为qisjskMql形式的单个“单词”，其中，qi表示的是初始状态，位于规则表的最左侧的一列，sj是在扫描区域被扫描的符号(空白被当作是符号的一种)，sk是在扫描区域将要被写上的符号，M表示扫描仪应该移动的方向，向左向右或停止(有些时候，一行中可能没有移动的指令，当没有移动的指令时则用“N”表示计算机停止)，ql是一个操作结束时的状态。将每一行的规则表改写成上述形式的“单词”，连接起来写成一行从而组成一长串的符号组合体编码命令，在两行规则表之间用分号分开[5]，在最后一行的规则表末尾用句号来表示一串符号组合体编码命令的完结。这个字符串能够转换成一串由A C D L R和N这些字母所组成的字符(还有分号)，图灵称之为机器的标准描述，以这种方式进行的变换过程能够使每个单一的指令从标准描述中找回。将A C D几个字母以不同的组合形式来代替原指令中的各种状态和各种符号，L R N则代表了扫描仪完成一个扫描区域的擦写程序之后应该向左向右或是停止所指代的符号。这样，一串符号组合体编码命令便被转换成为图灵所说的标准描述，并且标准描述能够转换为数字表示，称为描述数字。同样的，以这种方式进行转换，每个单个的指令能够从描述数字中找回。一个标准描述转换为描述数字的方法是将标准描述中的“A C D L R N ；”分别转换为“1 2 3 4 5 6 7”，这样，每一个标准描述都可被转换为描述数字。需要注意的是不同的标准描述能够描述同一个机器的行为，如，将两行规则表相互交换，这将不会影响机器在规则表下操作的行为，但是这将对接下来所得到的标准描述及其描述数字带来影响。

从上述情况可以看出，将一个规则表转换为一个标准描述或描述数字的这个过程类似于将一个计算机程序汇编为机器码的过程。程序设计者通常会选择在高阶语言中如Pascal、Prolog和C语言中工作。图灵所提到的规则表在高阶语言中汇编对于一个受过培训的人来说是相当简单的，在一个程序开始执行之前，指令码必须被翻译或者汇编为能够被电脑接受的形式(机器码)。

其三，是图灵对通用计算机及其运作的论述。图灵所说的通用计算机现在被称为通用图灵机，通用图灵机是存储程序电子计算机(现代计算机)的抽象概念形式。不是所有图灵机都是通用的，有一些图灵机只能执行某些特定的计算，只有通用图灵机才能够完成最一般的计算。能够模拟其他任何图灵机的图灵机称为通用图灵机，亦即通用计算机。通用计算机有一个单一、固定的指令规则表。在这个指令规则表下运行，通用计算机能够执行任何任务，并且其指令规则表都能够被写出来。

当我们谈到计算机程序的时候，它是有输入和输出的。读取一段程序即是输入，将得到的结果写出来即是输出。但是，图灵机是只有输出而没有输入的，原因是图灵机开始工作于一条无限长的空白纸带，输出数字数列和其他的一些符号。而通用计算机与图灵机不同，通用计算机要求在开始工作前输入某一台机器的标准描述，会写出和该台机器一样的输出，因此通用计算机相对于图灵机来说更为普遍、一般。

通用计算机是有一定复杂性的，然而，就如图灵所说的一样，通用计算机的最根本原则就是简单。以下为载入某个规则表指令的图灵机(这时机器的扫描仪处于计算机纸带的起始处，并且纸带是完全空白的)的例子，如果将一个机器的标准描述放置于通用计算机的纸带上，那么在纸带上特别标记的区域，通用计算机所输出的数列也是这个机器所输出的。通用计算机在它的纸带上以阅读指令来这样做，标准描述包括而且执行它们。为了使通用计算机工作，我们需要将这个机器的标准描述、初始状态和初始扫描区域的符号放在纸带上，除此之外，纸带上的其他区域都是空白的。然后，给该机器一个运行的刺激，则机器将会在纸带上留下一个记录。与图灵机不同的是，在纸带上不仅会有通用计算机所写的符号，而且还有计算时扫描仪每一步的位置、扫描仪显示的符号和每一步的状态。

图灵想要给通用计算机下一个普遍定义，他对数学过程能够被这种类型的计算机所实现进行了严谨的分析，他还介绍和分析了通用计算机的概念，如果任何数列能够被任何计算机所输出并且能够被这种特别的计算机所解决，则这个计算机便是通用的。一般而言，为了达到这个目的，它需要将不同的指令组合起来。这是图灵理论的主要成果[6]。

三、图灵可计算数思想的当代影响

冯·诺依曼和纽曼深受图灵的通用存储计算机理念的影响，这两位数学家和图灵本人是将图灵的抽象通用计算机变为现实的重要电子计算机工程师。

在第二次世界大战之后的几年，逻辑学家、数学家冯·诺依曼通过他的文章和公众演讲，使得存储程序数字计算机的概念广为流传。

1933年，冯·诺依曼开始在普林斯顿大学的一个高级研究院担任教授，冯·诺依曼和图灵第一次见面是在1935年4月，他与图灵相熟识是图灵在普林斯顿大学学习期间。图灵在普林斯顿大学的这段时间，冯·诺依曼对“论可计算数”的理论逐渐熟悉起来，他逐渐对图灵的通用计算机的概念变得很有兴趣。冯·诺依曼在他的论文《计算机和大脑》[7]中提到两个名字，其中一个是图灵，另一个是信息论的提出者克劳德·香农。显然，冯·诺依曼对图灵所做的工作是满怀敬意的。

物理学家富兰克尔(他和冯·诺依曼及其他人在参与自动化和氢弹的设计中使大型计算机机械化)记录了在冯·诺依曼思想中“论可计算数”的重要地位，大约在1943年或1944年，冯·诺依曼已经意识到图灵的《论可计算数在判决性问题中的应用》的重要地位，这篇文章在原则上描述了“通用计算机”，每一台生产出的计算机都是它现实化的版本。许多人都认为冯·诺依曼是“计算机之父”(在现在的眼光看来)，但是可以肯定的是冯·诺依曼从没有这样认为过。冯·诺依曼被称为计算机的助生者可能更为恰当，冯·诺依曼坚定地向所有人强调，最基本的概念属于图灵。因此，在笔者看来，冯·诺依曼的贡献就是使世界认识到图灵所介绍的计算机的基本概念，以及对摩尔学校(the Moor School)和其他地方的计算机发展所起的促进作用[8]。

1949年，在伊利诺斯州大学的一个名为“控制和信息的严谨理论”的演讲中，冯·诺依曼谈及图灵的研究的重要之处在于：如果你构建好了一台自动机，然后关于自动机的任何附加要求都能够以足够详尽说明的指令来处理。如果自动机足够复杂，并且它已经到达了最低要求的复杂性，那么这就是真的。换句话说，在给定合适的指令下，这种复杂的自动机能够做任何能被这个自动机执行的事情[9]。

冯·诺依曼将图灵的“通用计算机”的抽象概念介绍给许多美国工程师，但是在美国许多关于计算机历史的书中都没有提及图灵。毫无疑问，在许多技术性的报告中，关于计算机历史都没有涉及到图灵所做的工作，但冯·诺依曼和其他的合作者将逻辑性的设计融入了电子存储数字计算机之中，有证据证明在冯·诺依曼的文献中有关于“论可计算数”的知识。例如，在“电子计算机逻辑设计的初级讨论”的报告中，冯·诺依曼提到：“以形式逻辑的方法很容易看出，在理论上足够去控制和使其去执行的任何各自可适用于机器的操作数列出现的代码，在整体上都会被问题计划者所想到。从目前来看，在选择代码时的真正决定性的考虑因素更多的是一种现实性：设备的简易性由机器码所决定，和其应用到实际的重要问题的清晰度和处理问题的这些问题。”[10]这篇文章的第一句话就涉及到了图灵的通用计算机。

图灵对于现代计算机发展最为重要的贡献是控制一台计算机运行是通过存储一个代表性的程序，然后在计算机的内存中将程序编码为指令的理念；而且他证明用这种方法，一台固定架构的单一计算机能够执行每一个计算，并且这些计算能够被任何一台图灵机执行，也就是通用的。

图灵描述了通用计算机和存储程序电子计算机(现代计算机)之间的联系:有一种重要机制的机器包含无限纸带的存储空间，这表明这种单一特殊的机器能够做任何工作，这种特殊的机器可以被称为通用机器。当我们决定希望模仿怎样的机器时，我们就在通用计算机的纸带上给予它一个该机器的描述，这个描述解释了机器在每一个格局中将会如何做，在哪儿可以找到自己。通用计算机为了知道它在每一个阶段需要怎么做，它只有在这个给定的描述上不停地寻找适合当前格局的指令。因此，这个机器所做的工作的复杂性就是“集中于纸带上”(为指令规则表，其实就是软件)，“而且不应该以任何方式出现在通用机器中”[11]。

图灵所使用的用于图灵机的指令规则表就是现在称为计算机的程序。当他转而去设计一台电子计算机(ACE)时，图灵继续使用他的“指令规则表”这个概念，而现在的作者们用“程序”来代替它。类似ACE这样的计算机实际上是更加实际的通用机器，有一个确定的电子设备的核心区域和一个大的存储，当任何详细的问题需要被解决的时候，计算过程的合适指令将会存储在ACE的内存中，然后它就会运行来执行这个过程。

最初，图灵提出以十六进制来对将要输入计算机的指令进行编码，随着不断深入写程序的过程，他发现以二进制的形式来对其进行编码更为合适。就大规模的计算而言，使用二进制是很自然的事，在使用二进制之后，计算更为简单，因为制定只有两个固定位置的机制比制定多达十几个的固定位置的机制要容易得多[11]。然而，实际上真正重要的是，既然机器能够像人类那样执行计算且计算是人类思维的基本组成部分，那么机器是否能像人类一样思维呢？在图灵看来，这个答案是不言而喻的，他所提出的计算机在本质上与大脑并没有什么区别。

由大脑的生理构成我们可以看到，人类的大脑是由大量被称为神经元的成分组成，科学家们估计神经元的数量多达10亿或更多。这些神经元通过轴突和树突组成密集有线网络互相连接，就如一个巨大的网交织在一起，神经元可以看作为一种基本的开关，在任何情况下它都处于“开”或“关”的状态中。到底处于哪个状态取决于与它相连的其他神经元传来的信号。由此可以看出，计算机与大脑都能存储大量的基本数据，在计算机中是纸带上的0和1，而在神经元中是开和关的状态，关键是它们都能将这些数据处理成为某种模式。大脑的数据将以模式的形式来存储，这个模式是由神经元受到刺激而激发机制产生的。每种模式实际上是在某一时刻神经元的“开”和“关”的状态。而对于计算机来说，其数据存储在内存之中，其模式就是0和1的序列，这与状态的“开”和“关”没有区别。

大脑与计算机都能修改存储的值，前者通过不同的神经元被刺激，后者通过程序指令的修改。计算机相应于大脑的存储行为以及模式的改变是非常相似的。而正是这种相似性使得图灵相信在不久的将来可以建造出一台可以思维的机器。唯一的障碍不是在逻辑上，而是在技术上。从人类智能行为上来看，我们大脑的构成材料并没有什么特殊的物质，至少是在与思想有关的范围之中是这样的。从某种角度看来组成大脑的物质并非是真正的问题，真正的问题在于大脑的基本原件神经元究竟做了什么以及它们彼此怎样互相联系，才使得大脑具有认知能力。正是鉴于此，图灵提出了“模仿游戏”，即如果一台计算机被编程去和一个相当聪明的人进行一段对话，不管谈话提出的主题是否是有效的，只要无法简单地判断在与他或她谈话的是一个人或者是一个机器，图灵就说我们应该同意该计算机表现出了智能。从提出至今，图灵的模仿游戏招致了无数的争议，塞尔曾提出“中文屋”以反驳图灵；休·罗布纳在20世纪90年代初设立了人工智能年度比赛，将图灵的“模仿游戏”付诸行动；在不久之前，围棋人工智能程序AlphaGo在围棋比赛中成功战胜世界冠军李世石。然而直至现在，并没有一台机器可以通过图灵的“模仿游戏”测试，也没有任何测试可以取代模仿游戏成为机器能思维的标准测试。作为机器能思维的充分条件，图灵测试依然是人类实现自身以外智能而一直追求的目标。

图灵是一个对于现代社会有相当影响的人物，他论文中提出的“计算机”和“算法”两个核心概念在今天依然受用，他的“模仿游戏”测试依然作为测试机器能否思维的一个标准，他的通用计算机的设计理念和指令规则表的使用为后世计算机科学及其相关领域的发展奠定了基础，并使现代以信息为主导的社会的出现成为可能。

[1] HINSLEY H,STRIPP A.Codebreakers:the inside story of bletchley park[M].Oxford:Oxford University Press,1993:12.

[2] 马丁·戴维斯.逻辑的引擎[M].张卜天,译.长沙：湖南科学技术出版社，2006：64-65.

[3] TURINGA.On computable numbers,with an application to the entscheidungsproblem[G].Proceedings of the London Mathematical Society,1936:230-265.

[4] TURINGA.The t-function in λ-K-conversion[J].the Journal of Symbolic Logic,1937(2):42-43.

[5] MARTIN D.Mathematical logic and the origin of modern computers[M].Oxford:Oxford University Press,1988:149-174.

[6] VON NEUMANN J.The general and logical theory of automata[R].to be published.

[7] VON NEUMANN J.The computer and the brain[M].New Haven:Yale University Press,1958.

[8] RANDELL B.On Alan Turing and the origins of digital computers[M].[S.l.]:University of Newcastle upon Tyne,Computing Laboratory,1972.

[9] VON NEUMANN J.Rigorous theories of control and information[G]//Theory of Self-Reproducing Automata.Urbana:University of Illinois Press,1966:50.

[10]BURKS A W,GOLDSTINE H H,VON NEUMANN J.Preliminary discussion of the logical design of an electronic computing instrument[G]//The Origins of Digital Computers.[S.l.]:Springer Berlin Heidelberg,1982:399-413.

[11]CARPENTER B E,DORAN R W.AM Turing’s ACE report of 1946 and other papers[M].[S.l.]:Massachusetts Institute of Technology,1986.

(责任编辑 张佑法)

Discussion of Turing’s Computable Thought

HU Song

(College of Marxism,Central China Normal University, Wuhan 430070,China)

Turing’s computable thought has profound ideological origins, and the developments of Leibniz,Frege and Godel for artificial language has affected computable thought of Turing.The paperOncomputablenumbers,withanapplicationtotheEntscheidungsproblemhas proposed two abstract machines:Turing machine and general-purpose computer,and described basic structure and operation mode of both machines.Among them,general-purpose computer is the prototype of the modern computer;Turing’s computable thought fundamentally affected Von Neumann and thushelped him constructed the first computer. There is no substitute for Turing’s contribution to the development of the modern computer and machine intelligence.

computable thought;Turing machine;all-purpose computer;modern computer;machine thought

2016-09-12 作者简介：胡嵩(1991—)，男，湖北鄂州人，硕士研究生，研究方向：科学逻辑。

胡嵩.论图灵的可计算思想[J].重庆理工大学学报(社会科学)，2016(11):32-37.

format：HU Song.Discussion of Turing’s Computable Thought[J].Journal of Chongqing University of Technology(Social Science)，2016(11):32-37.

10.3969/j.issn.1674-8425(s).2016.11.004

B81-05

A

1674-8425(2016)11-0032-06