【偶尔灌下水】20世纪最伟大的智者之一 Alan Turing

Eastsun

§4.Turing生平

1912--
Alan Turing出生于1912年6月23日，伦敦.他的父亲 Julius Mathison Turing，是印度Br
itish Civil Service成员。他经常在国外。Alan的母亲Ethel Sara Stoney是Madras铁路
总工程师的女儿。Alan的父母在印度相遇，并在那儿结了婚。当Alan大约一岁时，他的母
亲在印度与丈夫相聚。而Alan留在了英国，与这个家庭的朋友待在一起。之后,Alan被送入
学校，但这似乎没有使其受到任何好处，因此，几个月后，他离开了学校。接下来，他又
被送往Hazlehurst Preparatory学校，在那儿，他在许多课程上获得了中上的成绩，但他
相当有主见。在学习生涯中他对棋类产生了兴趣，并且加入了辩论社。

1926--
他通过了常规入学考试，随后进入了学校。1926年，Turing恰遇大罢工，当罢工正进行中
，他骑车60英里从家来到学校。虽然母亲坚定的认为他必须接受公立学校的教育，但Turi
ng发现他很难成为学校所期望的那样。许多有独创思想的思想家发现学校是一个几乎无法
理解的过程，Turing便是一例。他的天赋驱使他朝自己的方向发展而无需老师。

Turing因书法而被批评，为英语而奋争，甚至在数学上他采用自己的方法而不用老师所教
授的解题法。在Sherborne 期间，尽管是非常规的方法，Turing仍然赢得了几乎所有的数
学奖。从早期起，Turing就对化学中的一个课题很感兴趣，他按自己的日程安排做试验，
这使得他的老师很不高兴。 Turing的校长认为：如果他留在公立学校,他必须以接受教育
为目标.如果他仅想成为科学专家，在公立学校就是浪费时间。这话远超出了对Turing自身
的意义，他说明了图灵所遇到的学校体制。虽然，他的老师可能并不清楚他在自学些什么
,但Turing在校期间学习了深奥的数学知识。他阅读了Einstein的关于相对论的论文，还通
过Eddington的“物质世界的性质”了解量子力学。

1928年，发生了影响Turing一生的事。他与Christopher Morcom年长其一岁的学生，产生
了亲密的友谊，并且两人共同工作于科学事业。也许，这是Turing第一次找到一位有共同
思想的人。可是Morcom于1930年2月去世。这对Turing是一个沉重的打击。在Morcom生病期
间，Turing就有死亡的预感。他感到这是科学无法解释的。之后，他写到：这些事实是不
难解释的，但我感到惊奇！

1931--
尽管学校这几年的艰难，Turing仍然1931年进入了剑桥皇家学院学习数学。这并非易事。
1929年，Turing参加了奖学金考试，他赢得了一个展现机会而非奖学金。因对这一结果的
不满，Turing在第二年又参加了考试，这一次他获得了奖学金。剑桥较其他学校对像这样
的非常规学生而言是一个相对较舒适的环境。他现在更能探索自己的思想，在1933年他读
了 的数学哲学入门。同时，他读了Neumann关于量子力学的1932年的文章。这是一个其一
生反复研究过的课题。

1933年，Turing开始对数理逻辑感兴趣。Turing读了一篇关于“数学和逻辑”的文章。他
提出数学的纯逻辑的观点是不足的，数学命题具有多种解释，逻辑只是一种。1933年，德
国希特勒上台，英国爆发了反战运动。Turing加入了反战运动，但他没有随波逐流去信仰
某些主义。Turing毕业於1934年，在1935年的春天,他参加了Max Mewman的关于数学基础的
高级教程。这一课程研究了Godel不完全性结果和Hilbert的可判定性问题。某种意义上来
说，可判定性是一个简单的问题，亦即给定一个数学命题，是否能找到一个决定命题是真
或假的算法。对于大多数命题来说，寻找这样一个算法是简单的。真正的难点在于证明对
于确定的命题，这样的算法不存在。当给出了一个解决某一问题的算法，很明显它确实是
一个算法，然而没有关于算法的足够严谨的定义使得可证明算法的不存在性。Turing开始
对这些问题进行研究。1935年，图灵因一篇关于高斯的误差函数（证明概率理论的基本结
果，亦即中心极限定理）的论文而当选为剑桥皇家学院的成员。虽然中心极限定理已被发
现，但Turing并不知道，他独立的发现了它。1936年, Turing成为一位Smith 奖得主。


1937--
现在，Turing在剑桥的成就被用来说明他在概率理论上的工作。然而，自从他参加了Newm
an的课程后，他就开始做可判定性问题的研究了。1936年,他发表了On Computable Numbe
rs, with an Application to the Entscheidungsproblem的学术文章。在这篇论文中，T
uring引入了抽象机的概念（现被称为Turing机）。Turing机利用有限的规则（由一张有限
表给出）及从带子上读入一个符号，从一种状态转换到另一状态。Turing机可输入或删除
带子上的一个字符。Turing写到：记录下的一些字符将会形成正在计算的实数的小数的数
字序列。其他的则只是一些粗略的符号用来”协助存储”，应被删除。

他将可计算数定义为小数扩展位可通过Turing机从空白带子产生的实数。他指出那即可计
算的，但由于仅可数的实数是可计算的，多数实数是不可计算的，因此，他给出了不可计
算的数的描述，并指出由于他在限定条件下描述了一个不能在限定条件下描述的数，从而
，这显得有些矛盾。但Turing明白这显然的矛盾的根源。给定指令表的Turing机是否输出
无限序列的数（用另一Turing机实现）是无法判决的。

虽然，这篇论文包含着对数学和计算机科学均有相当价值的观点，但在伦敦数学会学报上
发表它却不是那么容易的。原因是Alonzo Church 於1936年在美国数学期刊上发表了一个
初等数论不可解问题，同样证明对于算术无判定过程。Turing的方法与Church有相当的差
别，但在伦敦数学会期刊出版它之前，Newman为此费尽唇舌。Turing的修改稿提到了Chur
ch 的结果于1936年4月首次完成，同年8月修改的论文，这篇修改稿於1937年发表。

与Church讨论的好处在于，1936年Turing成为普林斯顿大学的研究生。在普林斯顿Church
的指导下, Turing了解了研究的方法。1938年,他返回英国。1937年，Turing回英国度暑
假邂逅Wittgenstein。他在普林斯顿的工作主要是基于序数的逻辑系统，发表于1939年。
Newman 认为：这篇论文充满了有趣的设想和观点……他展现了Turing的直觉及数学证明方
面的东西。

在这篇论文发表之前，Turing发表了两篇更常规的数学论题方面的论文。一篇是讨论通过
有限群逼近Lie群的方法，另一篇证明了扩展群的结果并给出了更简单和系统的方法。（R
einhold Baer首次证明了这一结果），Turing在Turing机上的工作最引人注目的是在现实
技术所能构造之前，他已描述了现代计算机。他在1936年的论文中证明通用Turing机的存
在：能用来做任何特殊目的的机器的工作，亦即若有恰当的指令输入，可进行任何计算。


尽管对Turing来说，“计算机”是一个执行计算的人，但我们必须从他对广义Turing机的
描述中看到我们今天的计算机加装有程序的带子即Turing机。在普林斯顿期间，Turing设
想过构造计算机。1938年，他一回到剑桥就开始构造analogue mechanical device 用来研
究Riemann 猜想，这是当今许多人认为的最难解决的数学问题。然而，在国家密码机构邀
请他回来破译德国密码之后，他的工作呈现出新的面貌。

1939--
当1939年二战爆发，Turing立即在政府设在Bletchley公园的译码和解码部门进行工作。虽
然官方对在那里开展的工作进行了严格的保密，但现在大部分内幕已被公开。Turing在密
码学和计算机方面的天才帮助破译小组破译了不少密码，拯救了无数士兵的生命。那一段
时间对于他是一生中最快乐的时间,充分发挥了他的才能。

Turing和另一位数学家Welchman一起在波兰数学家早期工作的基础上发展了Bombe机，这台
机从40年代末对所有从Luftwaffe的密码机发出的消息进行了译码。德国海军的密码机的编
码很难被破译，但这正是Turing所感兴趣的挑战。在1941年中期，Turing在统计学和信息
捕获方面的进展，使得德国海军的信号在Bletchley被破译。

从1942年11月到1943年3月Turing在美国进行解码和一个语音保密系统的研究工作。德国人
加密方式的改变意味着Bletchley失去了破译消息的能力。尽管Turing并没有直接参与到成
功破译更多的密码工作中，但他的思想的重要性在这项工作中得到充分体现。1945年, Tu
ring由于在战争中所作出的贡献而获得了OBE奖。

1946--
二战后，Turing被伦敦国家物理实验室邀请去参与计算机的设计。他在1946年提交了一份
关于自动计算机器的报告。用现代人的观点看来，Turing当时所提出的设想是一份有关计
算机的原始的详细设计。他为ACE(自动计算机器)设计的存储器的大小被当时大多数人认为
是毫无希望和过于夸张的，以至于在这个项目被批准前被耽误了好一阵。

在1947到1948学年Turing回到了剑桥，在那里他的研究兴趣不再是计算机和数学了，令人
惊奇的是，他竟然研究神经学和生理学。在这期间，他并没有忘了计算机，而且他还为计
算机编写代码。不过他的学术研究太广泛了，二战后他还认真研究了人类学。Walton运动
俱乐部记录表明，Turing作为会员曾赢得了3英里和10英里的冠军。1947年他参加了A.A.A
马拉松比赛，获得第15名。

1948年Newman成为曼彻斯特大学的数学教授，在那里他为Turing提供学者基金。于是Turi
ng从国家物理实验室回到了曼彻斯特。Newman写到：期望Turing能领导开展该项目中的数
学工作。一段时间能继续工作下去，为已建造好的机器设计例行程序，然后当这些工作稳
定后，继续数论分析方面的一般性问题研究。工作从由FC Williams 和 T Kilburn提出的
计算机的构造开始。

1950--
1950年，Turing在计算机和人工智能方面作出了极为卓越的成就。1950年，Turing发表了
里程碑式的论文“机器能思考吗？”，他预测了随着计算机发展将会出现的问题。他研究
了人工智能领域的核心问题。时至今日人们还用他发表的这篇论文中所提出的Turing测试
来尝试回答电脑是否具有智能。

Turing没有忘记判定性问题是他那些具有深远意义的数学论文的起点。群论中的一个主要
问题是：在一个有限群中给定任意一个字，是否存在一个算法判定这个字等于单位。Post
已经证明半群中不存在这样一个算法。虽然一开始Turing已经证明了对于群有同样一个结
论，但在就对他证明做一个讨论会上，他发现了一个错误。他从自己不完善的证明中发现
一个消去的半群有不可解字问题。Turing在1950年发表了这个结果。1957年勃恩通过Turi
ng的这篇论文中的思想证明了存在一个有不可解字问题的群。

主要因为在他1936年提出的“Turing机”方面所做的工作，Turing在1951年当选为伦敦皇
家学院的会员。到1951年为止，他致力于将数学应用到生物组织研究中去。1952年他公布
了在地貌形成方面，关于在有机生命体中模式和组织的演化的一部分研究工作。

1952--
1952年Turing在警察局报告一宗同性恋事件的细节时被捕，他被指控违反了英国同性恋法
令。而他去警察局是因为他遭到了勒索.1952年3月31日，他作为一位同性恋者被审判，他
认为他自己没错，未给自己辩护。然而，他被判为有罪。当时，他只有两条路可走：坐牢
或注射激素。他选择了后者，并继续他广泛的学术研究。

他不仅在地貌形成的研究中有进一步进展，而且他还在量子理论和相对论的研究中提出了
新的思想，即用旋量来表示初等粒子。在Bletchley公园的译码工作成了图灵在GCHQ进行译
码和人工智能研究工作的基础。在冷战期间，译码成为一项重要的工作，Turing继续为GC
HQ工作，尽管他在曼彻斯特的同事还没完全意识到这一点。在他被定罪后，他失去了安全
保障。但更糟糕的是，安全部门的官员将他这位知识渊博，在GCHQ开展工作的学者定为安
全方面的危险分子。由于学术需要，Turing有许多外国同事，但警察开始调查他的国外来
访者。1953年Turing在希腊的一次度假引起了安全人员的恐慌。1954年6月7日，Turing在
寓所身亡，他的床头有一个咬了一半的苹果，经解剖，发现是剧毒氰化物致死，那个苹果
是在氰化物溶液中浸泡过的，经调查，Turing为自杀，但他母亲始终认为这是一个偶然事
件。

§5.结束语

Turing不仅是一位数学家、逻辑学和计算机科学家，而且他更是一位哲学家，科学哲学家
，他问出：“什么是计算”以及“机器能思考吗”使我们受到哲学精神的震撼，他虽然是
这个尘世的匆匆过客，但他是勇敢的智者，他的发明将影响人类的思维，他是欧洲上空划
过的灿烂的流星。他是人类历史上的大智者。人们将永远怀念他，美国ACM设Turing奖，以
此纪念。

镇魂歌

偶看到傻掉.....-_-b

星界小记者

是的呀!快不行了!

Aragorn

我只看第一行和最后一行 不然我受不了

Anson

我居然看完了……拜Turing～确实很强～

Mrzeng

看完了..安息吧,Alan Turing,我的上帝

sohumaoggh

看了，不懂

谷虫

看标题后只想到4个字:人工智能
看到内容后就没耐心看下去了..

cassius

原来是图灵。。。。

汗，有名的图灵测试

Eastsun

宋方敏
（南京大学，计算机软件新技术国家重点实验室，南京，210093）

§1.引言

美国TIME杂志在1999年出版专卷介绍20世纪100个最伟大的智者，在计算机科学领域中英国数理逻辑学家Alan Turing列入其中（数学有Kurt Godel，物理有Albert Einstein,后来Einstein列为The person of the 20th century）。由于Turing对于人类的极出贡献，他成
为20世纪最有影响科学家和思想家之一。本文介绍Alan Turing的生平和主要工作，以此纪念计算机科学的奠基人。

§2. Turing评说

在数理逻辑的神秘王国里，一个天才提出了质疑和构想——设计一台能够模拟人类思维演
段的机器—— 一个天方夜谭？

如果Turing所做的一切只是回答了神秘的数理逻辑领域里的一个令人苦恼的问题的话，那
么就不会有什么理由让外行人记住他。但正相反，Turing使用他那给整个世界带来巨大影
响的方法，向世人展示——“一个封闭的逻辑系统里的某些命题是不能在本系统内得到证
明的”——这一曾令Kurt Godel名声大振的推论。这个年轻而前卫的剑桥大学学生所做的
就是梦想着造一台假想的机器——一台简洁而精巧，打字机模样的，可以扫描或读入那些
写在（理论上）无限长的磁带上的指令的机器。随着扫描器在磁带上移来移去——机器依
据指令按序执行或跳转，从而，Turing提出，机器执行过程的输出可以重现人类的思维。


这种受灵感启发的思想实验中的机器，连同Turing的另一个想法，很快获得了一个名字：
Turing机。因为磁带上的指令可以控制机器的行为，所以通过更换相应的指令就可以让这
台机器去完成所有这样的机器所能完成的任务。换句话说，通过扫描不同的磁带，同样的
一台机器既可以算题，又能下棋，还会做其它的相对更自然的任一件事.于是,他的机器又
赢得了一个更好听的新名字：通用Turing 机。

随着指令的运行，这样一台十分原始的硬件组合可以完成令人惊讶的各种任务。这样的想
法听起来可能吗？在1937年显然是无法想象的。那一年，Turing的学术论文On Computabl
e Numbers, with an Application to the Entscheidungsproblem发表在伦敦数学会学报
上。但是Turing的想法被很少的读者所理解,他们认为这些构思在理论上十分有趣和诱人，
却没有人认识到Turing的机器为后来的电子数字计算机勾画出了蓝图。

由于今天的计算机继承了如此之多的想法和技术上的创新，以至于我们无论将发明计算机
的功劳归在谁的头上都是鲁莽的。但事实是，每敲击一次键盘或打开一扇窗口，抑或是运
行一个字处理程序都是在一台Turing机的化身上工作。

Turing 1937年的论文改变了他的一生，让一个腼腆而脆弱的男人更多地被卷入到尘世中去，最终走向一个悲剧式的结局。

Alan Mathison Turing 1912年生于伦敦，是这个家庭的第二个孩子。他的父亲是印度Bri
tish Civil Service的成员，但他的母亲认为这样的环境不利于孩子的成长。于是Alan和
哥哥在英国的一个领养家庭中度过了他们的童年,除了偶尔回家看看，大部分时间和父母分
开。也许就是这其间Turing的孤独感诱发了他一生对人脑机理的兴趣——当上帝赐予的这
个世界显得贫瘠和令人不满的时候，怎样创造一个属于自己的世界呢？

Turing从13岁起就读于Dorset的Sherbourne小学，在那里，他已经显示出了自己的数学天
赋，尽管他的卷子总是因为杂乱无章而被批评。Turing在读小学的时候就发现了自己的同
性恋倾向，并爱上了学校里的另一个小男孩——虽然Turing从未告诉过任何人——后来这
个小男孩猝死于结核。这一事件粉碎了Turing的宗教信仰，使他成为了一个无神论者，并
让他坚信所有的现象都有一个客观的解释。机器没有思想，而大脑中也没有灵魂。那么，
思维和意识又是从何而来呢？

在两次向剑桥大学Trinity College 这所令全世界的数学家们神往的学府申请资助失败之
后，Turing 终于获得了 King’s College 的资助。在诸如 John Maynard Keynes 以及
E.M. Forster 这些名家泰斗们的指引下，King’s College 为 Turing 提供了充分自由与
宽松的环境。尽管他被King’s College的核心学术圈以行为不够检点的理由而拒之门外，
Turing还是得到了巨大的发展。并且当他获得了学位证书之后，Turing成了King’s Coll
ege的一名导师。而如果不是后来的Turing 机的诞生和二次大战的爆发，Turing恐怕只会
在数理逻辑的世界里慢条斯理、优哉游哉地生活一辈子了。

由于Turing发表的一系列论文，他被召入政府 Code and Cypher School。这所学院在一个
叫做Bletchley Park的维多利亚风格的大厦里。这里囫囵吞枣似的聚集了那些被认为有可
能攻破纳粹通信密码的人，包括数学家、国际象棋大师、古埃及研究学家等等。因为这项
工程受到了严格的保密，Turing在这里的工作直到他去世后才得以公之于众。正如计算机
的问世一般，Bletchley Park 的工作也是众人共同智慧的结晶。而Turing的角色更是重中
之重——他设计了一台原始的类似计算机的机器，用以高速破译北大西洋上纳粹U-艇间通
信的密码。

二战后，Turing回到了剑桥，他希望能够重新拾回他所向往的宁静的研究生活。与此同时
，国家物理实验室新近成立了一个数学分支——这个千载难逢的机遇使得Turing能够设计
出真正的Turing machine（即ACE —— Automatic Computing Engine）—— Turing 欣然
前往。然而事实并不如人意，官僚主义、繁文缛节，事不关己、高高挂起之风盛行于时。
战争年代里的那种晨兴夜寐、攻苦食淡的精神早已荡然无存。Turing 的提议不是被束之高
阁就是被全然否定。Turing 决定离开NPL，而后他在剑桥小憩，最终来到了曼彻斯特大学
。这里的实验室正在根据他1937年提出的构想建造一台计算机。

Turing自发表第一篇论文以来，就一直致力于拓展其关于会思考的机器的设想。他甚至提
出，一台会思考的机器可以学习并编制指令。1950年，在著名的英国哲学期刊Mind上，Tu
ring提出了“模仿测试”的概念（后来被称做“Turing测试”）。比如在一封闭的屋子里
，一提问人可以向另一个人与一台机器发问。若提问人不能通过二者的回答辨别出哪一个
是人，哪一个是机器的话，则这台机器就被认为能够象人类一样地“思考”。

Turing在人工智能支持者的心目中仍是一位英雄——其原因部分来自于Turing对未来的一
个乐观的估计：“未来的某一天，女士们带着她们的计算机在公园里散步，她们说：‘我
的计算机告诉我这真是个快乐的早晨！’”

不幸的是，美好的憧憬总让路于残酷的现实。在曼彻斯特的时候，一天他因遭抢劫而报警
，那时他正和另一个同性恋男子在一起，而这个人很可能为罪犯所认识。Turing 从不隐瞒
自己的同性恋倾向，但这次却使他身陷囹圄。同性恋在当时的英国仍是极重的罪名，1952
年，Turing 被判决为“严重猥亵罪”。不久他被减刑，并被要求注射雌性荷尔蒙以去除其
同性欲望。一次，Turing对他的朋友说：“我变得越来越有女人味了！”在1954年6月7日
，Turing食注有氰化钾的苹果自尽, 当时他只有41岁。


§3. Turing机简介

Alan Turing 在1936提出了非凡的Turing机概念，从而定义出可计算性，Turing的思法是
基于对人们用笔和纸来实现一个算法的分析，他把这样的过程看作下列两种非常简单的动
作。

（1）写上或擦去某个符号。
（2）把注意从纸的某个部位转移到另一个部位。

而在每个阶段，算法说明下一次要做的动作。这样就依赖于（a）行为者当前观注的纸上某
个部位上的符号和（b）行为者思维的当前状态。为了达到实现算法的目的，假定这完全由
此算法以及迄今为止的运算记录来确定。这可能为编入一个部分的记录，但这不反映行为
者的心情、智力和理解力。而且由于行为者是有穷的，故他只能处于有穷个互异状态。当
然行为者的状态能转为此阶段已执行的动作。Turing以此法设计一种有穷机器来执行算法
，后来这类机器被称为Turing机。

下面我们给出Turing机的定义。一个Turing机M是一个有穷装置其在一条纸带上执行运算。
这条纸带向两端无限延伸且在两个方向上都已画上了无穷多个方格。（参见图１）

图1

纸带代表人类行为者算题时的纸，而每个方格代表即时运作的一个部分。在运算时只有有
穷格被利用，但我们事先不知道要用多少个格子。纸带是无穷的代表人类在计算时可无限
量提供白纸。在任何时刻，纸带上的每个方格要么空白，要么含某个符号，这些符号取自
M的字母表固定的一列符号S1，S2……Sn。下以B表示空白且把B看作S。属于M的字母表。M
有一个读头，它在任何时候都扫描着纸带的单个方格。（参见图２）

Ｍ q 当前状态
读头

S3 S2 S1


正被扫描的方格
图２

M可在纸带上进行三种简单动作：
1.擦去正被扫描方格的符号且把它换成M字母表中的另一符号。
2.把读头移至正被扫描方格的右边的方格。
3.把读头移至正被扫描方格的左边的方格。

在任何给定时刻，M处于某个状态，M的状态总共有有穷个，可设为q1,…,qm，在运作中，
M的状态是可变的。我们可设想M的当前状态q展示于M的外体上（参见图2），认为此q既部
分指导当今做了什么以及今后将做什么。

在任何时刻M采取的行动取决于M的当前状态以及正被扫描的符号，这样的依赖关系被用M的
说明来描述，M的说明Q是由有穷个四元组构成，每个四元组呈下形：qisjskql,qisjRql,q
isjLqlp这里1≤i,l≤m,O≤j,k≤n,Q中的四元组qisjαql说明当M处于状态qi且正扫描于S
j时M将采取的动作如下：

1.带上运算
1.1.若α＝Sk则擦去Sj,同时在当前方格中写上Sk
1.2.若α＝R，将读头向右移一格
1.3.若α＝L，将读头向左移一格

2.转成状态ql
M的说明Q需要对每个对qisj至多存在一个呈形qisjαβ的四元组于Q中，否则会导到M下个
动作的不确定。

为了进行计算，必须为M提供一条纸带以及确定M当前所扫描的方格，而且指定M的初始状态
。然后，假设M当前状态为qi且正扫描符号Sj,若在M的说明Q中，有呈形qisjαql的四元组
，则M将如上所述地动作。这种动作将重复于新状态和正被扫描的符号，M将尽可能地如此
进行下去。M的动作终止仅当其状态为qi且正扫描着Sj使Q中不存在呈形qisjαβ的Q元组，
即Q中无四元组其指示下一步做什么，当然这种情况永不发生。

例.该M的一个Turing机其字母表为{B，O，1}且其可能状态为q1和q2，M的说明为

q10Rq1
q110q2
q20Rq2
q21Rq1

假设为M提供的纸带为

1 1 1 1 1 1 1 1
状态为q1
α=q118
α→q2017
α→0q217
α→01q116
α→01q2015
α→010q215
α→0101q114
α→……
α→010101q111
α→010101q201
α→0101010q21
α→01010101q1B

0 1 0 1 0 1 0 1
若为M提供的纸带的每个方格为0或1，则M不停机。

由上例可看出，Turing机M是在纸带上实行算法的一个装置，算法的全部内容含于M的说明
Q中理论上，Turing机被定义成某个Ｑ元组集合，而不是实际上构造的物理Turing机。


为了把Turing机当作计算数论函数，我们首先在纸带上表示数，例如设Ｍ的字母表中含１
，把１看作“小木棒”，用连续的n+1个“１”表示n。

B 1 1 1 … 1 B
n+1个1
约定， =1n+1,对于m元组（n,……,nm）,其对应的带表达式为
定义：设f为从Ｎ到Ｎ的部分函数，Turing机Ｍ计算f(n)指若为Ｍ提供上面的纸带，初始状
态为q１且箭头标出正扫描的方格，则
=

对于m元部分函数f(x1,…,xm),M计算f指M始于状态q１且提供如下纸带且由箭头指出正被扫
描的方格：

Ｂ 1 … 1 B 1 … 1 B … B 1 … 1 B
x1+1 x2+1 xm+1

若Ｍ计算终止则f(x1, …,xm)为带上１的总数否则f(x1, …,xm)无定义。

例 加法n+m可由如下的Turing机计算：

Ｍ的字母表为{Ｂ，１}，Ｍ的说明Ｑ为
q11Bq1
q1BRq2
q21Bq3
q2BRq2
情况１：n≠0
q11n+1B1m+1→q1B1nB1m+1→Bq21nB1m+1→Bq3B1n-1B1m+1停。
情况２：n=0
q11B1m+1→q1BB1m+1→Bq2B1m+1→BBq21m+1→BBq3B1m

定义：一个部分数论函数是Turing可计算的指存在Turing机其计算之。这样就定义了什么
是可计算的。由以上知n+m是Turing的计算的，事实上Turing的计算能力非常强大，一切的
递归函数都是Turing可计算的，可以证明任何一种程序设计语言所能计算的函数一定是Tu
ring可计算的，为此现在人们接受Church-Turing论点：一切可直觉可计算的函数是Turin
g可计算的。