计算机算不了的函数是什么样的？ 马耀基 现在人工智能很热，人们在争论计算机会不会有一天真正具有智慧，超越人类。我们目前还不知道这个问题的答案，但确实知道计算机有很多事情做不了，就连有的函数计算机都算不了。不是人类能力有限设计不出程序来算它们，而是在理论上这些函数就是无法计算的。（可计算，可用计算机计算，可用程序计算，这些概念在本文是同一个意思。） （注释 1 ） 插一句，说起无法计算的函数，我想起一道数学题：请写出一个无法画出图像的函数。 （注释 2 ） 开始觉得神奇，竟然有这样的函数？看了答案后觉得很简单。这里说的不能计算的函数也是一样，看似不可思议，其实很容易理解这些函数为什么不可计算，甚至无需懂得编程，当然第一个人想到这些函数很困难。 举个例子。我们要画一棵树，使得这棵树和世界上所有的树都不一样。假设所有的树都是绿色的，我们只要把它画成黄色的就行了。但用这种方法，你要知道现有的树共同特征是什么。但就算对树一无所知，理论上我们也知道能画出一棵与众不同的树。我们把全部的树进行编号，然后这样设计这棵新树：它在高度上跟 1 号树不同，叶子数量跟 2 号不同，树枝长短跟 3 号不同，……，总之它和每一棵树都最少有一个地方不同。同样，是否存在不能计算的函数呢？回答这个问题我们无需知道具体的可计算的函数长什么样，只要能设计出和每个可计算函数都不同的函数就行了。 我们能画出不同的树，是因为画上的树比真实的树多，与此类似，我们能找到不可计算的函数，本质上是因为函数比程序多。 这篇文章主要的目的是介绍两个不能计算的函数，并且说明它们为什么不能计算。 1 、函数 先复习一下什么是函数。 y=x+1 ， z=x+y ，两者都是函数，前者是一元函数， x 是自变量， y 是因变量。后者是二元函数，其中 x 、 y 是自变量， z 是因变量。为什么它们是函数呢？因为自变量的值确定时，因变量有唯一的值与之对应，比如 y=x+1 中，当 x=1 时， y=2 ，当 x=2 时， y=3 ，而函数 z=x+y 在 x=2 ， y=3 时， z=5 。在函数中，自变量的值确定了，允许因变量不取任何值，但不允许因变量的取值超过一个。比如函数 y=10/x ，当 x=0 时， y 不取任何值，这时说函数在 x=0 处没有定义。 x 2 +y 2 =1 ，这个方程不是以 x 为自变量的函数，因为 x=0 时，对应的 y 有 1 和 -1 两个值，同样它也不是以 y 为自变量的函数。 什么是函数？如果当自变量的值确定时，因变量有 0 个或 1 个值与之对应，那这些变量间的关系就构成了函数。自变量只有 1 个时，就是一元函数，两个时就是二元函数，由此类推。 无法计算的函数，是指不存在这样的程序：当输入自变量的值时，程序 总是 输出这个函数的因变量的值。 2 、程序 一个计算函数 y=x+1 的程序，就是输入 x 的值，输出 y 的值，即如果输入 2 ，它就输出 3 ，如果输入 5 ，它就输出 6 。如果计算的是二元函数，输入的是两个数，输出的结果还是一个数。 有些程序是 不会结束的，它陷入死循环，永远运行下去。比如有一个程序，当输入数字小于 10 时，它将这个数字加 1 ，然后输出，如果输入的数字大于或等于 10 ，它就不停地进行加 1 运算，永远不停下来。那这个程序计算的是这个函数：当 x10 ， y=x+1 。当 x=10 时， y 无定义。 每个程序都计算一个函数。当函数有定义时，程序输出函数值，当没有定义时，程序永远不结束。 （注释 3 ） 我们给所有的计算机程序分配号码（或叫编码），这些号码都是自然数。就像每个人都有不同的身份证号码一样，每个程序也有不同的号码。这里编码的不单是指现在世界上存在的所有程序，而是指理论上所有可能的程序，这样的程序数量显然是无限的。 （注释 4 ） 每个程序都可以分配不同的号码，看上去是显而易见的事情。实际上并非如此，比如我们就无法给每个实数分配号码，因为实数的数量太多了。程序能够编码，这是需要严格的证明的。这里省略证明，我们直接接受这个结论。 因为所有的程序都是可以编码的，所以所有计算一元函数的程序也可以编码。我们把计算一元函数的程序称为一元程序。 3 、无法计算的函数 我们这里构造两个无法计算的函数，一个是反对角线函数，一个是程序结束函数。思路大概这样： 给所有一元程序编码，这些程序对应了所有能计算的一元函数。因为按前面的定义，能计算的函数就是能用程序计算的，而所有的一元程序都在这里了，所以可计算的一元函数也全在这里。构造一个函数，这个函数与任意一个可计算的一元函数，都最少一个在某一个输入值时输出不同。这个函数叫反对角线函数。反对角线函数和所有可计算的函数不同，所以是不可计算的。 另一个是程序结束函数，它能判断任一个程序在任一个输入下是否结束。程序结束函数是无法计算的。有两种证明方法。 1 、如果程序结束函数能够用程序计算，那反对角线函数就能计算。 2 、如果程序结束函数能够用程序计算，那就能设计出一个程序，当这个程序把自己的号码作为输入时，会出现矛盾。 下面具体讨论这两个函数。 为了简单，我们这里考虑的函数，变量都是自然数。 A 、反对角线函数 给所有计算一元函数的程序分配号码，将这些程序记为 P 1 ， P 2 ， P 3 ，…… P n ，……，每个程序对应着一个可计算函数。 现在构造反对角线函数 d ， d 的定义是这样的： d(n)=2 ，如果 P n (n)=1 ， d(n)=1 ，如果 P n (n) ≠ 1 ，或者 P n (n) 无定义。 （ P n (n)=1 ，表示当输入为 n 时，程序 P n 的输出是 1 。） 函数 d 的值总是和下表对角线中的不同，所以叫反对角线函数。 函数 d 与任何一个程序所计算的函数都不同。因为 n=1 时， d(1) ≠ P 1 (1) ，在 n=2 时， d(2) ≠ P 2 (2) ，……， n=m 时， d(m) ≠ P m (m) 。所以函数 d 是任何一个程序不能计算的。 还可从另一个角度思考，如果 d 是可计算的将导致矛盾。假设它是可计算的，则计算它的程序必然分配有号码，假设是 s ，则函数 d 就是程序 P s 计算的函数， P s (s) 的值是什么？按照定义，如果 P s (s)=1 ， d(s) ≠ 1 ，但程序 d 就是程序 P s ，所以矛盾。同样，如果 P s (s) ≠ 1 ，也有矛盾。 这里的证明关键是程序可以用自然数编码，如果这个条件不成立，证明就无效了。因为定义 d(n) 的值时，要用到 P n (n) 的值，这需要先给程序分配号码才知道 P n 是什么。 B 、程序结束函数 （也称图灵机停机函数） 反对角线函数为什么不能计算呢？看上去似乎是可以计算的，先判断 P n (n) 是否有定义。如果 P n (n) 无定义，则 d(n)=1 ，如果 P n (n) 有定义，就运行程序 P n ，看输入为 n 时 P n 的输出是多少，然后根据规则给 d(n) 赋值。 困难在于判断 P n (n) 是否有定义，即输入为 n 时，程序 P n 是否结束。如果能设计出一个判断程序，对任意的 n 它都能判断 P n (n) 是否结束，则反对角线函数 d 就是可计算的。因为我们知道函数 d 无法计算，所以这样的程序是不存在的。这个（不存在的）判断程序所对应的函数是程序结束函数，也叫图灵机停机函数，它是不可计算的。 程序结束函数 h ，具体来说是这样的： h (m,n)=1 ，如果程序 P m 在输入 n 时，最终会结束。 h (m,n)=2 ，如果程序 P m 在输入 n 时，永远不会结束。 （注释 5 ） 我们还可以从另一个角度思考这个问题。 可以证明，如果存在计算函数 h 的程序 H ，则我们能构造出一个程序 G ，当程序 G 把自己的号码作为输入时会出现矛盾。 程序 G 是这样的。 输入 m ，程序 G 运行程序 H(m,m) ，如果 H(m,m) 输出 1 ，则 G 永远不结束，如果如果 H(m,m) 输出 2 ，则 G 结束。 程序 G 是计算一元函数的，所以 G 也有一个号码，假设这号码是 t ，即程序 G 就是程序 P t 。输入 t 时， G(t) 会结束吗？按定义，如果 P t (t) 结束，则 h(t,t)=1 ，则 G(t) 不结束永远运行。但程序 P t 就是程序 G ，矛盾。同理， h(t,t)=2 时，也会导致矛盾。所以程序 G 不存在，因此程序 H 不存在。 注释： 1 、这篇文章说的计算机是指图灵机，我们现在所用的计算机本质上都是图灵机。按照丘奇图灵命题，可计算函数和图灵机可算的函数这两个概念是等价的。 2 、这样的函数很多，比如狄利克雷函数：当 x 是有理数时， y=1 ，当 x 是无理数时， y=0 。 3 、假设有一个程序，当输入 x 不等于 0 时，它输出 y=10/x 的值，当输入 0 时，输出“输入错误”。严格来说，它算的不是 y=10/x ，它算的是另一个函数，这个函数在 x ≠ 0 时，和 y=10/x 一样，但 x ≠ 0 时， y 仍然有取值。如果算的是 y=10/x ，则 x=0 时，程序不结束。 4 、不同的程序，功能可以是相同的。比如程序 A ，对输入的变量先加 1 ，再加 2 ，然后将结果输出。程序 B 则是先加 2 ，再加 1 。程序 A 和 B 是不同的，所以它们分配到的号码是不同的，但是功能相同。 5 、有人可能会疑惑，当输入为 (m,n) 的时候，判断程序将 m 解码成相应的程序，然后再判断这个程序在输入 n 时是否结束，这样的判断程序 H 为什么不能存在呢？假设这样的判断程序存在，它在判断 P m (n) 是否结束时，有时候要运行 P m (n) ，如果 P m (n) 永远不结束，程序 H 不知道它暂时还没算完，还是永远算不完，因此程序 H 只好继续等待，什么也不输出。因此程序 H 计算的肯定不是函数 h ，因为函数 h 对任意的 n 都有定义。 科学花果山 相关文章 从理发师悖论到计算机的极限
从CiE2016会议（ https://lipn.univ-paris13.fr/CIE2016/index.php ）回来了，或许可以用“相见恨晚”来形容与CiE2016的相遇吧！有来自欧美近百个学者参会，会议给我的第一印象就是洋溢着一种忧患意识，为此，我不得不再说Barry Cooper（1943--2015），是他与同道一起创建CiE系列会议及“Association Computability in Europe（可计算性在欧洲协会）”，并且他是“图灵百年纪念活动（Alan Turing Centenary)”的推手，。。。 2003年，Barry提议创建一个学术网络，他说［1］： －2003年，基于阿兰·图灵的科学遗产，我创办了一个叫“可计算性在欧洲”的“书呆子”学术网络，并企图得到欧盟的资助，结果失败了。 « In 2003 I founded a geeky academic network called Computability in Europe (CiE), based on Alan Turing’s scientific legacy, and attempted - unsuccessfully - to get EU funding. » 关于图灵的科学遗产，Barry说到［1］： « 。。。The end of that year （1936）saw the publication of a thirty-six page paper by a young mathematician, Alan Turing, claiming to solve a long-standing problem of the distinguished German mathematician david Hilbert. A byproduct of that solution was the first machine-based model of what it means for a number-theortic function to be computable, and the description of what we now call a Universal Turing Machine. 。。。 What is less often remembered is Turing’s theoretical contribution to the understanding of the limitations on what computers can do. There are quite easily described arithmetical functions which are not computable by any computer, however powerful. And even the advent of quantum computers will not change this. » Barry提醒人们，图灵1936年的那篇奠基性文章是为证明著名的“判定问题”而提出图灵机的，但是后来人们只关注图灵论文的副产品－图灵机，而不大记得图灵的初衷了，为此Barry欲创建“可计算性在欧洲”的学术网络，希望能回归图灵的精神。 然而他们的提案几次遭拒，评审报告认为他们的提案过于集中在传统的可计算性理论，而没有留意“新的计算范式”，但是这样的拒绝却成为Barry及同道坚定发展“可计算性”研究的决心和行动。 抱持着这样的决心，Barry在2007年提出举办“图灵百年纪念活动”的倡议，并坚持2012年的CiE会议在英国的剑桥（Cambridge）举行，Barry任图灵百年纪念活动的顾问委员会主席（Turing Centenary Advisory Committee，TCAC），将“图灵百年纪念活动”推向了世界！待“图灵百年纪念活动”结束，Barry不愿到此终止，又将“Alan Turing Year”变成了“Alan Turing Years”，。。。 Barry与CiE一路走过曲折的十几年，却不幸于去年（2015）离开人世，“饮水不忘挖井人”，今年CiE会议的主题之一是纪念Barry Cooper。 参考资料： 1，Benedikt Löwe，Barry Cooper (1942-2015): The engine of Computability in Europe »，Computability, the Journal of the Association CiE, Vol 5, Number 1, 2016.
我们的NP理论以哲学和中国思想为指导，建立在可计算性理论的基础上。我周一（6月27日）去巴黎参加“可计算性在欧洲国际会议”（ https://lipn.univ-paris13.fr/CIE2016/index.php ），现简介会议，与大家分享： 一，会议简介 CiE（Computability in Europe，可计算性在欧洲）是一个跨学科的国际年会，旨在促进与可计算性相关的学科的发展，包括数学、计算机科学及各种自然和工程学，如物理学和生物学方面的应用，也包括关于计算的哲学和历史的研究。 今年的CiE会议在巴黎举行（June 27th 2016 - July 1st 2016），其口号是：“通用的追求（Pursuit of the Universal）”。今年也是图灵的奠基性论文《论可计算数及其在判定问题上的应用》（ On Computable Numbers, with an Application to the Entscheidungsproblem）发表80周年，论文提出的图灵机为诸学科，如证明论、人工智能、广义可计算性、型信息和自然语言的基本角色、可计算性和可定义性支持的生物信息学等，指出了发展方向。会议提出口号“通用的追求（Pursuit of the Universal）”，是为纪念图灵对跨越科学和人文的通用计算框架的追求。 二，S Barry Cooper, 1943--2015 Barry Cooper是“可计算性在欧洲协会（Association Computability in Europe）”的创始成员和前主席，已经于2015年10月26日去世。 Barry Cooper是英国逻辑学领军人物，也是可计算性理论尤其是度理论（degree theory）的重要学者。Barry Cooper是图灵百年纪念活动的顾问委员会主席（Turing Centenary Advisory Committee，TCAC），多年积极推动和倡导回归图灵提出的基本问题，发展与可计算性相关的跨学科。鉴于近些年可计算性的相关研究未受到学术界应有的重视，Barry Cooper于2005年在阿姆斯特丹主办了第一届CiE2005，遂有如今拥有上千人的“可计算性在欧洲协会”。 今年CiE2016会议的主题之一是纪念Barry Cooper。 三，会议论文集 附上会议分Conference proceedings和Abstract Booklet，也可在会议网址上可以查阅。 bfm%3A978-3-319-40189-8%2F1.pdf abstract-booklet.pdf
“可计算性（Computability）”是可计算性理论的核心概念，具有深刻的数学内涵和哲学底蕴，图灵、丘奇、哥德尔等前辈的工作为此概念打下了坚实的基础，应该说对此概念的理解已经不成问题了，然而从“NP是可计算的”流行观念看，此概念并未得到人们充分而正确的解读，这或许是造成千禧年难题“P versus NP”的最根本原因。 我们从回答“什么是可计算性？”说起，来解读学术界流行观点的回答，指出“可计算性”蕴含着“机器”与“问题”二个不同的层次： 一，学术界回答“什么是可计算性？”的典型答案 1，维基（ https://zh.wikipedia.org/wiki/可计算性 ） 可计算性（calculability）是指一个实际问题是否可以使用计算机来解决。 2，维基（ https://en.wikipedia.org/wiki/Computability ） Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation. 3，Michael Sipser的书“Introduction to the Theory of Computation” 此书是计算理论领域的经典著作，常被大学选为教材。书中干脆就不谈“可计算性”，直接用“可计算函数”代替（p. 234）： COMPUTABLE FUNCTIONS：A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape. 4，Stanford Encyclopedia of Philosophy（ http://plato.stanford.edu/entries/computability/ ） A mathematical problem is computable if it can be solved in principle by a computing device. 二，解读“可计算性（Computability）”与“可计算的（computable）” 可见，上述回答实际上是在答“什么是可计算问题（computable problem）？”，而不是直接答“什么是可计算性（Computability）？”，那么，我们不禁要问：“computability”与“computable problem”是一回事吗？ 对于“computable problem”的标准答案是由丘奇－图灵论题给出的（https://en.wikipedia.org/wiki/Church–Turing_thesis）： J. B. Rosser (1939) addresses the notion of effective computability as follows: Clearly the existence of CC and RC (Church's and Rosser's proofs) presupposes a precise definition of 'effective'. 'Effective method' is here used in the rather special sense of a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps. Thus the adverb-adjective effective is used in a sense of 1a: producing a decided, decisive, or desired effect, and capable of producing a result. In the following, the words effectively calculable will mean produced by any intuitively 'effective' means whatsoever and effectively computable will mean produced by a Turing-machine or equivalent mechanical device. Turing's definitions given in a footnote in his 1939 Ph.D. thesis Systems of Logic Based on Ordinals, supervised by Church, are virtually the same: † We shall use the expression 'computable function' to mean a function calculable by a machine, and let 'effectively calculable' refer to the intuitive idea without particular identification with any one of these definitions. The thesis can be stated as follows: Every effectively calculable function is a computable function. Turing stated it this way: It was stated ... that 'a function is effectively calculable if its values can be found by some purely mechanical process.' We may take this literally, understanding that by a purely mechanical process one which could be carried out by a machine. The development ... leads to ... an identification of computability† with effective calculability. († is the footnote above, ibid.) “如果一个函数的值能被某个纯粹的机械过程求得，那么此函数就是能行可计算的”，可见，“可计算函数”是须要前提的，此前提就是存在着一台可以求解函数值的机器，换句话说，“可计算性”涉及到“问题”与“机器”二个层次，“机器的能力”为本，“问题的性质”为末。于是，用“可计算问题”代替“可计算性”，实际上是忽略了“可计算性”蕴含的二个层次的关系，从而造成认知混淆，。。。 所以，对于“可计算性”的理解应该回到对“机器的能力”的认知上，即回到对“图灵机”的认知上来。追本溯源，“图灵机”是在图灵1936年那篇重要论文《论可计算数及其在判定问题上的应用》（ On Computable Numbers, with an Application to the Entscheidungsproblem）中提出来的，让我们一起回到这篇具有历史性意义，但又令人望而生畏，至今使人无法深入的奠基性的论文。 三，《论可计算数及其在判定问题上的应用》中关于“图灵机”的论述 图灵在论文中开门见山指出，“按照我的定义，一个数是可计算的，如果它的十进制的表达能被机器写下来。”就是说，图灵强调预期的结果一定要被机器写下来，才能认为一个数是可计算的。 接下来，他开始设计这样的机器，将之称为“computing machine”。于“Computing machine”，图灵又区分了“circular machine”和“circle-free machine”，“circular machine”是因某些因素如“死循环”而无法写下计算结果的机器；而“circle-free machine”没有这样阻碍，能写下预期结果，换句话说， “circle-free”表达了图灵称之的“可计算性（computability）”。 然而，一个问题是否“computable”须要判断，这就是图灵这篇奠基性的论文的主题，回答“可计算性的判断”，进而回答著名的希尔伯特第十问题，。。。 让我们回到问题：“什么是可计算性？”，相对于流行答案“可计算性是指一个实际问题是否可以使用计算机来解决”，应该说：“可计算性是指算法（图灵机）具有解决一个实际问题的能力”，“可计算问题是指存在着具有可计算性的算法的问题”。。。 附： 1，图灵论文“On Computable Numbers, with an Application to the Entscheidungsproblem”原文： https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf 2，《论可计算数及其在判定问题上的应用》的前言，第一，二章部分译文： “可计算数”简单说是，其十进制的表达用有限的手段可计算的实数。虽然本文的主题表面上讲可计算数，然而几乎可以同样容易定义和研究变量为整数或实数或可计算变量的可计算函数，可计算谓词等。在每种情况下，基本的问题是一样的，我选择可计算数来解释，是因为这样可以涉及最少的技术细节。不久我希望给出可计算数与可计算函数等之间的关系，这将包括用可计算数表达的实数变量的函数理论。按照我的定义，一个数是可计算的，如果它的十进制的表达能被机器写下来。 在§9,10，我给出一些论点，想指出可计算数包括所有的能自然看作可计算的数。比如，它们包括代数数的实数部分，Bessel函数的大小的实数部分，PI, e等等。然而可计算数并不包括所有可定义的数。 尽管可计算数类如此之大，在许多方面类似于实数类，它仍然是可枚举。在§8章，我调查某些证明似乎证明相反的论点。通过正确应用一个论点，可达成一个与哥德尔的结论表面上相似的结论。这些结果可有价值的应用，尤其是，指出（§11）Hilbertian Entscheidungsproblem没有解。 The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine. In §§ 9, 10 I give some arguments with the intention of showing that the computable numbers include all numbers which could naturally be regarded as computable. In particular, I show that certain large classes of numbers are computable. They include, for instance, the real parts of all algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers X, e, etc. The computable numbers do not, however, include all definable numbers, and an example is given of a definable number which is not computable. Although the class of computable numbers is so great, and in many ways similar to the class of real numbers, it is nevertheless enumerable. In §8 I examine certain arguments which would seem to prove the contrary. By the correct application of one of these arguments, conclusions are reached which are superficially similar to those of Gödel . These results {231} have valuable applications. In particular, it is shown (§11) that the Hilbertian Entscheidungsproblem can have no solution. 1，计算机器（Computing machine） 我们已经说过，可计算数是那些可用有限的手段计算而得的表达为十进制的数，这需要较明确的定义。在第九章之前，不对定义作真正合理化的说明，目前我仅说理由是人类的记忆需要限制。 可将一个在计算实数的人与某机器比较，此机器具有有限数目的状态：q1;q2;…qk（m-格局，m-configurations）。给机器提供一条纸带（类似纸张），机器在上面运行，纸带被分为段（方格，squares），每个方格上放置一个符号。在任何时刻，只有一个方格，比如第r个方格，放置符号了S（r），“在机器里”，我们可以称此方格为“扫描方格”，“扫描方格”里的符号称为“扫描符号”，“扫描符号”是机器“直接感知”的唯一符号。然而，通过变化格局，机器可以有效记忆已经“见过（扫描）”的符号。机器在任何时刻可能的行为由m－格局qn，扫描符号S（r）决定，这对（qn，S（r））称为“格局”：于是，格局决定机器可能的行为。在有些格局，扫描方格是空的（即没有符号），机器就在扫描方格上写下一个新的符号；在别的格局，它擦掉扫描符号。机器也可能改变正在扫描的方格，但是仅仅向左右移动一个方格。此外，对任何一个这样的操作，m－格局可能变化。某些写下的符号将形成数字序列（ sequence of figures），它是正在计算的表达为十进制的实数，别 的符号只是“辅助记忆”的粗糙纪录，只有那些粗糙纪录可能被擦掉。 我的观点是，这些操作包括了所有用在计算一个数时所需的操作，为此论点辩护要在读者较熟悉机器理论后才会较容易。在下一节，我将着手发展此理论，假设读者已经知道“机器”，“纸带”，“扫描”等。 1. Computing machines. We have said that the computable numbers are those whose decimals are calculable by finite means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach §9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited. We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1, q2, ..., qR which will be called “m-configurations”. The machine is supplied with a “tape”, (the analogue of paper) running through it, and divided into sections (called “squares”) each capable of bearing a “symbol”. At any moment there is just one square, say the r-th, bearing the symbol S(r) which is “in the machine”. We may call this square the “scanned square”. The symbol on the scanned square may be called the “scanned symbol”. The “scanned symbol” is the only one of which the machine is, so to speak, “directly aware”. However, by altering its m-configuration the machine can effectively remember some of the symbols which it has “seen” (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration qn and the scanned symbol S(r). This pair qn, S(r) will be called the “configuration”: thus the configuration determines the possible behaviour of the machine. In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or 1eft. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down {232} will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to “assist the memory”. It will only be these rough notes which will be liable to erasure. It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by “machine”, “tape”, “scanned”, etc. 2，定义 自动机（Automatic machines） 如果每个阶段机器的运动（在第一章的意义上）完全由格局确定，我们称此机器为«自动机»（a-machine）。 为了某种目的，我们可能使用一些机器（choice machines or c-machines），它的运动部分由格局决定。当这样的机器到达一个这样模棱两可的格局时，只有当外界的操作做某个任意的选择，它才能继续运行。如果我们用机器处理公理系统时会出现这样的情况，在本文中，我只处理自动机，因此往往忽略前缀a-。 计算机器（Computing machines） 如果一台机器打印两类符号，第一类（称为数字）全是0和1，其它被称为第二类符号，则机器将被称为“计算机器”。如果给机器装置一条空白纸带，让它运动起来，从正确的初始m－格局出发，机器打印的第一类符号的子序列称作“机器计算的序列”；在表达为二进制的十进制实数前放上小数点，称作“机器计算的数”。 在机器运动的任何阶段，扫描方格的数，在纸带上所有符号的完整序列，及m－格局，被说成是描述那时刻的“完全格局”。机器和纸带在一系列完整格局之间的变化被称作“机器的运动”。 循环和非循环机器（Circular and circle-free machines） 如果计算机不再写下有限数目的第一类符号，被称作“循环（Circular）”；否则，被称作“无循环（circle-free）”。 如果一台机器达到一个格局，从此不再运动，或者即使继续运动，只能打印第二类符号，而不能打印任何第一类符号，此机器则是“circular”。“circle-free”的意义将在第8章解释。 可计算序列和可计算数（Computable sequences and numbers） 一个序列被说成“可计算的”，如果能够通过一台“circle-free machine”计算而得。一个数是可计算的，如果它与由“circle-free machine”计算的数只差一个整数。 我们应该避免混淆，说可计算序列比说可计算数更经常。 2. Definitions. Automatic machines. If at each stage the motion of a machine (in the sense of §1) is completely determined by the configuration, we shall call the machine an “automatic machine” (or a-machine). For some purposes we might use machines (choice machines or c-machines) whose motion is only partially determined by the configuration (hence the use of the word “possible” in §1). When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore often omit the prefix a-. Computing machines. If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine. At any stage of the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the m-configuration will be said to describe the complete configuration at that stage. The changes of the machine and tape between successive complete configurations will be called the moves of the machine.{233} Circular and circle-free machines. If a computing machine never writes down more than a finite number of symbols of the first kind it will be called circular. Otherwise it is said to be circle-free. A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term “circular” will be explained in §8. Computable sequences and numbers. A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle- free machine. We shall avoid confusion by speaking more often of computable sequences than of computable numbers.
标签: 可计算性
