我的书签
添加书签
移除书签阿兰·图灵在其论文第1节的开头（本书第59页）定义可计算数时写道：“在§9之前，我们不会真正尝试证明这个定义的合理性”。现在，我们讲到第9节了，图灵传记作者安德鲁·霍奇斯将论文的剩余部分誉为“有史以来数学类论文中最不寻常的部分”。［1］
图灵试图论证，图灵机的计算能力等同于一部执行明确定义了数学过程的人类计算者。因此，如果算法过程是图灵机不可解的，那么它对于人类而言也是不可解的。这个想法后来得名图灵论题，也称为邱奇-图灵论题。称其为“论题”是因为它是个过于模糊的概念，不能接受严格的数学证明。这个论题还被扩展到了其他数字计算机上，这些计算机的计算能力都没有图灵机强。
本章只会讨论第9节的第一部分，阅读第9节的其余内容需要数学逻辑知识，本书的第三部分再对其进行阐述。对于大多数内容，我不会打断图灵本人的分析。以下是马丁·戴维斯的总结。
图灵的“分析过程”是应用哲学的一个精彩展现。在这个分析过程里，图灵以人类如何进行计算开始，摒弃了无关的细节，简明扼要地得到分析结果，这个结果就是大家熟悉的运行在单向无限长线性纸带上的有限状态机模型。［2］
[249]
9. The extent of the computable numbers.
No attempt has yet been made to show that the “computable” numbers include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically. The real question at issue is “What are the possible processes which can be carried out in computing a number?”
The arguments which I shall use are of three kinds.
(a) A direct appeal to intuition.
(b) A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).
(c) Giving examples of large classes of numbers which are computable.
9. 可计算数的范畴
现在还未证明，“可计算”数包括所有被自然当做可以计算的数字。所有能给出的论据本质上都局限在直觉上，没有令人满意的数学说服力。真正有争议的问题是：“对数进行计算的可能的过程有哪些？”
我能给出的论据有三类：
(a) 直觉的引导；
(b) 关于两种定义等价的证明（新的定义有更多的直觉成分）；
(c) 给出大量可计算数的示例；
(b) 论据将在本书第三部分讨论，(c)论据在图灵论文的第10节有进一步阐述。
Once it is granted that computable numbers are all “computable”, several other propositions of the same character follow. In particular, it follows that, if there is a general process for determining whether a formula of the Hilbert function calculus is provable, then the determination can be carried out by a machine.
一旦承认所有的可计算数都是“可以计算的”，便会产生具有相同特征的另外一些命题。特别是可以得出，如果存在可以判定希尔伯特函数演算的方程是否可证明的通用过程，那么这个判定就可以用机器进行计算。
“希尔伯特函数演算”就是今天数学逻辑体系里的“一阶谓词逻辑”。希尔伯特在这种逻辑下定义判定性问题。图灵不太可能知道“用机器进行计算”的过程就是海因里希·贝曼之前谈及判定性问题时提到的观点（第40页）。贝曼的论述直到最近才发表。
I. [Type (a)]. This argument is only an elaboration of the ideas of § 1.
Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent†. The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral such as
[250]
17 or 999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an enumerable infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.
† If we regard a symbol as literally printed on a square we may suppose that the square is 0 ≤ x ≤ 1, 0 ≤ y ≤ 1. The symbol is defined as a set of points in this square, viz. the set occupied by printer's ink. If these sets are restricted to be measurable, we can define the “distance” between two symbols as the cost of transforming one symbol into the other if the cost of moving unit area of printer's ink unit distance is unity, and there is an infinite supply of ink at x = 2, y = 0. With this topology the symbols form a conditionally compact space.
I. [类型(a)]。这个论据只是对§1观点的详细阐述。
计算通常可以通过在纸上书写某些符号来完成。我们可以假设这张纸就像小孩子的算术书，分成一个个方格。在初等算术中，有时会利用纸的二维性。但是，这种做法总是可回避的，并且我认为，大家应该认同纸的二维特性对于计算并不重要。我假定计算是在一张一维的纸上完成的，例如在一条分成方格的纸带上。另外，假设可打印符号的数目是有限的。如果我们允许数目是无限的，那么将会存在一些差异程度任意小的符号。†限制符号数目并不会有严重的影响，因为总是可以使用符号序列代替单个符号。通过这种方法，像17或999999999999999这样的阿拉伯数字将被认为是单个符号。类似地，任何欧洲语言里的单词都被当做单个符号（但是，汉语倾向于拥有可枚举的无限的符号）。在我们的观点里，单一符号和组合符号的区别在于，太长的组合符号不能一眼就识别出来。这是与我们的经验相一致的。我们不能一下子辨别出9999999999999999与999999999999999是否是同一个数。
† 如果我们认为一个符号是打印在一个0≤x≤1，0≤y≤1的方格内，那么可以将这个符号定义为这个方格内一系列点组成的集，即被打印点墨占据的点集。如果这些点集是可测量的，且将单位面积的打印点墨移动单位长度的开销是统一的，我们可以将两个符号的“距离”定义为将一个符号变换为另一个符号的开销，而在x = 2，y = 0的地方有无限量的点墨。在这种拓扑结构下，符号有条件地组成了一个紧凑的区域。
下一句话里，图灵谈到了“计算机”，当然，他指的是人类“计算者”。
The behaviour of the computer at any moment is determined by the symbols which he is observing, and his “state of mind” at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be “arbitrarily close” and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.
计算者任一时刻的行为都由彼时他观察到的符号和彼时他的“思维状态”决定。我们可以假设，对于符号的数目或者计算者在某一个时刻所能观察到的方格，存在一个上限B。如果他想观察到更多，就必须继续观察。我们也假定，需要考虑的思维状态的数量是有限的。这样做的理由和限制符号数目的理由是相同的。如果我们允许思维状态是无限的，那么它们之中有些状态将会因“无限地接近”而造成混淆。同样地，这种限制不会对计算造成很大的影响，因为避免使用更复杂的思维状态时可以通过在纸带上写上更多的符号来实现。
1972年，库尔特·哥德尔针对这节中图灵的分析写了短评，称其为“这是图灵分析中的一个哲学错误”。［3］哥德尔认为，“图灵分析里所指的思维并不是静止的，而是持续变化的”，而且精神上的思维状态可能会更加趋于无穷。这种分歧代表了对“思维最终是来自于大脑的机械过程”持正反观点的两派之间的基本冲突。
Let us imagine the operations performed by the computer to be split up into “simple operations” which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always “observed” squares.
Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square.
In connection with “immediate recognisability”, it may be thought that there are other kinds of square which are immediately recognisable. In particular, squares marked by special symbols might be taken as imme-
[251]
diately recognisable. Now if these squares are marked only by single symbols there can be only a finite number of them, and we should not upset our theory by adjoining these marked squares to the observed squares. If, on the other hand, they are marked by a sequence of symbols, we cannot regard the process of recognition as a simple process. This is a fundamental point and should be illustrated. In most mathematical papers the equations and theorems are numbered. Normally the numbers do not go beyond (say) 1000. It is, therefore, possible to recognise a theorem at a glance by its number. But if the paper was very long, we might reach Theorem 157767733443477; then, further on in the paper, we might find “… hence (applying Theorem 157767733443477) we have …”. In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure, possibly ticking the figures off in pencil to make sure of their not being counted twice. If in spite of this it is still thought that there are other “immediately recognisable” squares, it does not upset my contention so long as these squares can be found by some process of which my type of machine is capable. This idea is developed in III below.
我们想象一下，把机器的操作分解成“简单操作”，即最基本的操作，以至于不能想象它们能够再分解。每个这样的操作都是由计算者及其纸带组成的物理系统的变化构成的。如果我们知道纸带上的符号序列，就知道了系统的状态，这些都是由计算者（通过特定次序）和计算者的思维状态观察到的。我们假设在一个简单操作里最多有一个符号会改变。所有其他的变化都可以分解成这种简单的变化，其中，符号会被改变的那些方格的情况与被观察到的方格相同。因此，我们可以不失一般性地假设，符号变化的方格总是那些“被观察”的方格。
除了这些符号上的改变，简单操作还必须包含被观察方格分布的变化。新的被观察方格必须可以立即被计算者识别。我想可以合理地假设这些方格满足它们与最近的前一个立即被观察方格的距离不超过某个特定值。我们假设每个新的被观察方格距离前一个立即被观察方格的距离不超过L个方格。
谈到“立即识别”，也许存在其他类型的被立即识别方格。特别地，用特殊符号标记的方格可能被认为是立即识别的。若这些方格是由单个符号标记的，那么这样的方格数目就是有限的，可以遵循我们的理论将这些被标记的方格毗连到被观察的方格边。另一方面，如果标记方格的是序列符号，我们就不能将识别过程当做是一个简单过程。这是一个应该强调的基本出发点。在绝大多数数学论文里，方程和定理都是附上标号的。通常，这些标号不会超过1000，因此扫一眼标号就能迅速识别一个定理。但是如果论文很长，标记的定理可能到157767733443477号，接着我们可能要表述为“……因此通过应用157767733443477号定理，我们得到……”。为了确定相关定理，我们需要一位一位地比较两个数，可能需要用铅笔将比较过的数字划掉以免重复算两次。如果除了这些还存在其他“立即识别”的方格，只要这些方格可以在我的机器的运行过程中找到，也不会与我的论点相违背。这个观点会在第III部分进一步阐述。
当图灵说“用铅笔将比较过的数字划掉”时，他很可能指的是用非数字符号“标记”方格这样类似的机器操作。
The simple operations must therefore include:
(a) Changes of the symbol on one of the observed squares.
(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.
It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following:
(A) A possible change (a) of symbol together with a possible change of state of mind.
(B) A possible change (b) of observed squares, together with a possible change of state of mind.
The operation actually performed is determined, as has been suggested on p. 250, by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation is carried out.
因此，简单操作必须包括：
(a) 改变一个被观察方格的符号。
(b) 将一个被观察方格移动到与前一个被观察方格距离L以内的位置上。
这些改变有可能涉及一系列思维状态的转变。因此，最普遍意义上的单个操作必须是下列情况之一：
(A) 一个可能的(a)型的符号改变以及一个潜在的思维状态转变。
(B) 一个可能的(b)型的被观察方格的改变以及一个潜在的思维状态转变。
第250页已经说过，操作实际上是由计算者的思维状态和被观察的符号所决定的。特别是，操作执行后，计算者的思维状态就确定了。
这些只是他对论文前一页的引用。
We may now construct a machine to do the work of this computer. To each state of mind of the computer corresponds an “m-configuration” of the machine. The machine scans B squares corresponding to the B squares observed by the computer. In any move the machine can change a symbol on a scanned square or can change any one of the scanned squares to another square distant not more than L squares from one of the other scanned
[252]
squares. The move which is done, and the succeeding configuration, are determined by the scanned symbol and the m-configuration. The machines just described do not differ very essentially from computing machines as defined in § 2, and corresponding to any machine of this type a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the computer.
我们现在可以构造一台做这种计算者工作的机器了。对于计算者的任意一个思维状态，机器都有相应的一个m-格局。对应计算者观察B个方格，机器扫描B个方格。对于任意一次移动，机器要么改变被扫描方格上的符号，要么将任意一个被扫描方格移动到距离其他被扫描方格距离不超过L的位置。当完成移动后，后续的格局都由扫描符和m-格局决定。这里描述的机器与§2定义的计算机器并没有本质的区别，对应于任意这一类机器，都可以构造一个计算机器去计算相同的序列，也就是由计算者计算的序列。
这就是，人类计算者。
我们暂且在这里打住。图灵在本节的第二个论据从对“受限希尔伯特函数演算”的引用开始，接着对这个演算进行了陈述，为开始阅读本书第三部分提供一些背景知识。
图灵对人脑和机器之间联系的着迷，在1936年发表可计算数论文之后仍延续了很久。图灵的另一篇著名论文“计算机械与人工智能”发表在1950年10月的哲学期刊Mind上。
“机器能思考吗?”图灵问。他发明了一个测试，这个测试需要一个人坐在电传打字机前（在现代，类似于短消息，或者其他允许人们在看不见也听不见对方的情况下相互通信的手段）。这个人问问题，接受答案。如果另一端是计算机，而这个人无法判断它是否是一台计算机，那么就说计算机是具备人类智能的。
这就是著名的图灵测试，它至今依旧存在争议。任何对图灵测试有适当反对意见的人都应该读一读图灵的论文，里面有对很多合情合理的反对意见的解答。
图灵喜欢用术语“智能”而不是“思考”来处理这个问题，因为“思考”暗含在计算机内部进行的特定活动。
“机器能思考吗?”我认为，这个原始问题过于无意义，不值得讨论。不过，我认为到这个世纪末，这样的说法以及一般的教育观点都会有很大改观，那时候再谈及机器思考将不会受到抵触和反对。［4］
上个世纪末已经过了，若说有什么改观，那就是比以往任何时候都多的人知道了计算机能够干什么，但那不是“思考”。我们还未到可以期待计算机媲美人类智能的地步，并且在通常情况下，当我们认为计算机应用能以一种完全确定的形式运行时才能很好地运用它进行工作。一个尝试做任何“智能”工作的计算机程序通常就像个2岁的孩子，盯着一幅新画的蜡笔壁画，然后诉求“我想你会喜欢它的”。
在科幻小说的世界里，图灵预言成真，就像下面描述的一台有史以来最著名的虚构计算机：
哈尔能否思考的问题已经被英国数学家阿兰·图灵在20世纪40年代解决了。图灵指出，如果一个人能够与一台机器进行一次足够长的对话，无论是通过电传打字机还是麦克风都不重要，假如不能分辨回答是来自一台机器或者一个人，那么从感性的定义上，这台机器就是能思考的。哈尔能够轻易通过图灵测试。［5］
如果图灵能够活到56岁，也就是1968年《2001：太空漫游》的小说和电影发行的时候，他也许会感到十分有趣，因为计算机已经相当智能，能够体验到精神崩溃。
1950年夏天，图灵搬到了位于曼彻斯特以南10英里的威姆斯洛。他对形态形成学产生了兴趣，这是一门研究组织细胞如何发展和分化，形成各种各样模式和形态的物种学科。这个研究涉及在曼彻斯特的计算机上运行仿真程序。
1951年3月15日，阿兰·图灵因其在可计算数方面所做的工作，成为英国皇家学会的会士，举荐他的是麦克斯·纽曼和伯特兰·罗素。那天晚上，BBC播放了图灵题为“数字计算机能够思考吗？”的录音谈话（这个广播的录音和其他图灵所有讲话的录音都已不知所踪了）。
1951年12月，接连发生的一系列事件对日后产生了很大的影响。图灵在曼彻斯特的街上遇见了一个年轻人阿诺德·穆雷。工人出身的穆雷正处于偷窃罪缓刑期，也没有工作。图灵和穆雷共进了午餐，一起回到了图灵的家里。在接下来的一个月，他们还相会了几次。
1952年1月底，图灵发现住所遭窃。他报了警，警察检查了现场的指纹。图灵指控阿诺德·穆雷行窃，而穆雷声称自己是无辜的，并指认真正的罪犯是自己的一个旧相识哈里。警方也在图灵的住所找到了哈里的指纹。哈里彼时因为其他一些事情正在坐牢，在被问到图灵一案时，哈里告诉了警方图灵和其朋友间一些很私密的情况。
1952年2月7日，就在乔治六世驾崩，他的长女伊丽莎白继位的隔日，警方传讯了阿兰·图灵。在几轮审讯后，图灵承认了与穆雷之间的关系。这个供认让图灵遭受了牢狱之灾，因为根据1885年的刑法修正案第11节：
任何男性，公开或私下，组织或参与组织，引诱或试图引诱其他男性进行严重猥亵的行为，都应该视为不法行为，并理应被法庭判处不超过2年、可带劳役或不带劳役的监禁。［6］
法律并没有定义“严重猥亵”的概念，但通常指的是诸如手淫和口交之类的行为。其他法律还就更严重的肛交行为（即“鸡奸”，英国司法系统里用了这个术语）制定了刑律。
恶名昭著的刑法修正案第11节从一开始就颇受非议。1885年的刑法修正案自称是“一部进一步保护妇女和未成年少女，抑制妓院和其他恶习的法律”。这部法律将少女法律上达到可以自主的年龄从13岁提高到了16岁，包含了一系列措施保护妇女免受利用，诸如在色情场所被下迷药、被拐为娼等犯罪行为的侵害。
这个法律提案最初在下议院多年未获准，后来因为自由主义新闻记者威廉·托马斯·斯特德（1849—1912）关于儿童卖淫的一系列报道文章而变得引人注目。斯特德以从一对父母手中购买他们13岁的女儿为代价，让他这个大胆的揭发报道名噪一时。
在斯特德报道引发的强烈公众舆论下，该提案死灰复燃。第11节是由下议院议员Henry Labouchere在1885年8月6日提出的，而第二天就被加进了该提案中，一星期后，该议案最终通过。当时有一些疑问，质疑第11节是否适合加进这样一部核心是用来保护年轻女子和妇女的法律中。［7］
第11节特别针对男性，而在此之前，法律指的“严重猥亵”行为在英国并不是违法的，至少成年人私下进行是没问题的。甚至在那时，“私下”这样的条款似乎容易造成利用法律进行敲诈勒索。［8］
对于第11节，最著名的受害者是奥斯卡·王尔德（1854—1900），他于1895年被告发。王尔德因此被迫服劳役，这可能加速了他的离世。
到了20世纪50年代，刑罚方法变得多样了。图灵为自己的罪名辩护，法庭最后判处图灵1年缓刑，在此期间图灵必须接受荷尔蒙治疗。
使用荷尔蒙治疗同性恋的实验始于20世纪40年代。起初，同性恋行为被认为是因为缺少足够的男性荷尔蒙激素，但睾丸激素的实际效果却与预期的相反。接着，雌性荷尔蒙激素被用于男性同性恋，结果似乎更能达到预期的目的。［9］在图灵被定罪的那个年代，这种疗法被称为器官疗法，也称为“化学阉割”，这似乎比任何其他行为更让人觉得羞辱。雌激素治疗让图灵失去了性能力，让他的乳房畸形生长。
在20世纪50年代初被认定为是同性恋可就糟了。在美国，50年代初麦卡锡主义下的“赤色恐惧”很快转变为另一种形式上的政治迫害。在美国国务院工作的共产主义者其实并不多，反倒是政府部门私下里有同性恋倾向的人较多。“20世纪50年代到60年代间，大约有1000名国务院的工作人员因所谓的同性恋行为而被开除”。［10］
理论上，“危险分子”是用来形容有泄漏国家机密倾向的人。但实际上，这个词是“同性恋者”的委婉说法。［11］这种臆断是假定同性恋者容易遭到敲诈而泄漏国家机密。然而，现实中能找到这种假定的最好例子，还得追溯到第一次世界大战之前奥地利情报机构的一位头目，而且这个故事的真实性还一直存疑。［12］
美国政府对同性恋的做法影响到了英国政府。1951年，美国国务院开始建议英国外交部注意政府里面的“同性恋问题”，后来施压英国政府更多地关注可能由同性恋引起的安全问题。［13］
阿兰·图灵的择业自由因此变得很狭窄。政府最高机密的工作，例如战时图灵从事的工作，是绝不可能了，图灵也不可能再一次去美国。1952年的一部美国法律禁止“患有精神错乱人格的外国人”入境，暗指的就是同性恋。［14］
所有的这些足以导致图灵自杀吗？我们不清楚。
在英国的大街小巷以及政府部门，同性恋者的生活变得愈发艰难。当约翰·诺特-鲍尔爵士1953年被任命为伦敦大都市警察局局长时，他发誓要“铲除伦敦所有肮脏的场所”。同年，英国内政部指示要加大对“男性堕落行为”的打击力度。至少，伦敦的当地治安官已经厌倦了对犯罪的纵容态度，打算让罪犯“像过去一样直接被送回监狱里”。1953年年末到1954年年初，报纸的头条都是在宣传某些男性被告发的消息。［15］
是不是图灵与某位男性发生了新的关系，那人反过来威胁敲诈图灵？
或者如他母亲所说，图灵的自杀纯属意外？
关于图灵这一时期的精神状态，一个有说服力的解释竟来自于小说而不是历史文献或者自传资料，这说明我们对这段史实的无知。小说家珍娜·列文（也是巴纳德大学的天文和物理教授）描绘了这个受到难言羞辱的人：
他并不知道该如何表达甚至感受他受到的屈辱。这种屈辱像一个损坏的部件在他的身体里震荡着，喋喋不休，瓦解摧残着他的骨架。这种屈辱感不能得到平息，也不能在内心深处沉淀，那样的话，即使痛苦会化脓，但至少这种屈辱感会被隔离在内心深处，甚至可能治愈。他的心理分析医生即便能帮他减轻这种痛苦，但若没有一段长久的时间持续为他轻抚打磨伤口，这种痛苦的感觉可能会激烈地爆发。这种屈辱就是不能深埋下来。［16］
我们不知道1954年6月7日的晚上发生了什么不一样的故事。我们也不知道是什么驱使图灵在睡觉前，将每晚都要吃的苹果蘸上了氰化物。
第二天早晨，图灵被发现已经过世，年仅41岁。
