丘奇－图灵论题（Church–Turing thesis）

计算机理论的基础是可计算性理论，而可计算性理论的基石是“图灵机”与“丘奇－图灵论题”。丘奇-图灵论题是一个关于可计算性理论的假设，该假设论述了关于函数特性的，可有效计算的函数值，即在算法上可计算的。任何算法都可以由一台图灵机来执行，即以任何编程语言编写的算法都可以被翻译成一台图灵机，反之亦然，因此任何一种编程语言都足够用来有效的表达任何算法。简而言之就是“任何在算法上可计算的问题同样可由图灵机计算”。

​ 上个世纪末，深蓝凭借前所未有的搜索和判断棋局的能力，成为第一台战胜人类国际象棋世界冠军的计算机，但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识；而到了现在，AlphaGo却已经能凭借自己的算法，通过自我对弈，不断搜索最优解来提升自己的棋艺，其强大之处在于，通过“强化学习”来积累技能，去除了人类认知水平的局限性，跳出了原有的框架，创造出了原创型的最优步骤。而这一切，都来源于越来越精巧的计算。

​ 计算似乎无所不能，宛如新的“上帝”。但即使是这位“上帝”，也逃不脱逻辑设定的界限。第一位发现这一点的，便是图灵。

可计算函数

​ 可计算函数是可计算性理论研究的基本对象。可计算函数是算法的直观概念的形式化模拟，在某种意义上，如果存在可以执行函数工作的算法，则函数是可计算的，即给定函数域的输入，它可以返回相应的输出。可计算函数用于讨论可计算性，而无需参考任何具体的计算模型，如图灵机或注册机。但是，任何定义都必须引用某些特定的计算模型，但所有有效定义都会产生相同的函数类。产生可计算函数集的可计算性的特定模型是图灵可计算函数和递归函数。

​ 在精确定义可计算函数之前，数学家经常使用有效计算的非正式术语。从那时起，这个术语就被可计算的函数所识别。注意，这些函数的有效可计算性并不意味着它们可以被有效地计算，即在合理的时间内计算。事实上，对于一些有效可计算的函数，可以证明，任何计算它们的算法在算法的运行时间随着输入的长度呈指数甚至超指数地增长的意义上将是非常低效的。可行的可计算性和领域计算复杂性研究可以有效计算的函数。

​ 根据丘奇－图灵论题，可计算函数正是可以使用机械计算设备计算的函数，给定无限量的时间和存储空间。同样，论题指出，当且仅当它具有算法时，函数才是可计算的。在这种意义上的算法被理解为具有无限时间和无限量供应的笔和纸的人可以遵循的一系列步骤。

图灵计算模型

​ 哥德尔指出完备的形式化数学系统是不存在的，在此研究成果的影响下，20世纪30年代后期， A. M. Turing从计算一个数的一般过程入手，对计算的本质进行了研究，从而开始了对计算本质的真正认识。

​ 简单来说，图灵机是一个逻辑机的通用模型。图灵机由一个控制器、一个读写头和一个无限长的存储带组成。处理器实际是有限状态控制器，能使读写头左移或右移，并对存储带进行修改或读出。于是通过有限指令序列就能实现各种演算过程。图灵机模型将可计算性这一概念与机械程序和形式系统的概念统一起来。

​ 图灵机模型的实际意义在于：图灵证明，只有图灵机能解决的计算问题，实际计算机才能解决；如果图灵机不能解决的计算问题，则实际计算机也无法解决。即可计算性=图灵可计算性。因此，图灵机的能力概括了数字计算机的计算能力，对计算机的一般结构、可实现性和局限性产生了深远的影响，甚至于新一代量子计算机也仍是以图灵机为原型。

丘奇-图灵论题

​ 丘奇-图灵论题最早来源于图灵和丘奇关于判定性问题能否被解决的证明，当时丘奇首先利用递归函数和“可定义”函数来形式化地描述了有效可计算性，紧接着图灵证明了“判定性问题”是不可解的，根据丘奇对有效可计算性的描述，图灵又证明了图灵机所描述的是同一集合的函数。对这一论题的观点进行延伸，可以得出一个结论：数学和逻辑学中的所有有效运算方法均可以用一台图灵机来表示和演算，通常这些方法需要满足：

• 由有限多的精确指令组成，每一条指令都可以由有限多的符号来描述；
• 每个方法都会在有限步骤内产生结果；
• 该方法的执行不需要人类的智慧理解，即只需要按照给出的指令计算即可得出结果；

​ 图灵机与当时哥德尔、丘奇、波斯特等人提出的用于解决可计算问题的递归函数、Lambda演算和POST规范系统等计算模型在计算能力上是等价的。在这一事实的基础上，形成了著名的丘奇—图灵论题：一个自然数上的函数 f:N^n→N 是能行可计算的（effectively computable），当且仅当它是图灵可计算的（Turing computable）。

​ 此论题虽无法证明，但也从未被推翻。图灵机出现以前的计算设备，比如算盘和其他机械式运算设备，虽然也是通用的“计算机”，但它们不可能像图灵机那样执行所有的计算任务。另外算盘的“程序”只能储存在演算者的大脑里,而图灵机存储的程序成为计算机自身的一部分，这就是很重要的区别。

​ 在哲学方面，丘奇-图灵论题的意义非常深刻，涉及到宇宙的本质和超计算的可能性。广义的丘奇-图灵论题认为宇宙是一台图灵机，可以存储无限精度的实数，如果这样定义，则宇宙中不存在实数，只存在可计算数；由上，如果该定义为真，则在物理上对非递归函数的计算是不可能的。

忙碌的海濑

​ 一个有名的例子是Busy Beaver函数。该函数接受输入n，它输出的值是具有n个状态的图灵机，在停机之前所能够在纸带上写下的“1”的最大的个数，并且这些1之间没有任何空隙，也定义它输出的值代表n个状态的图灵机停机之前所走出的最大步数。停机问题在图灵机上是不可判定问题。找到Busy Beaver函数的上限等于解决停机问题，这是图灵机无法解决的问题。由于图灵机无法计算Busy Beaver函数，因此丘奇-图灵论题指出该函数不能使用任何方法进行有效计算。

超计算模型

​ 现在我们讨论任何一种东西的计算能力，最后基本都是归结为和图灵完备的。那么有没有可能有一种机器是比图灵机的模型更强的，可以实现计算一些图灵机上无法计算的内容。而他们被称为超计算（Hyper computation）模型。

​ 超计算或超图灵计算可以输出非图灵可计算结果的计算模型。例如，一台可以解决停机问题的机器可算作一台超计算机。超计算机能计算图灵机无法计算，即丘奇－图灵论题中不可计算的的函数。由图灵本人亲自提出的谕示机，是一种用来研究决定型问题的抽象电脑。可以被视为一个比广义图灵机多了个黑盒子的图灵机，这个黑盒子的功能是可以在单一运算之内解答特定问题。预言者可以解答的问题，根据给定可以是任何复杂度类之内的问题。甚至可以使用不可判定问题，像是停机问题。

结语

“为什么把‘计算机科学’称为‘科学(Science) ’，而不是‘工程(Engineering) ’？”

“因为有了‘计算理论’，从此计算机不仅仅只是一门工程了，而是变为科学了。”——我们“计算理论”老师如是说。

​ 丘奇-图灵论题最伟大的地方在于辨清了计算，图灵机和编程语言的关系。把计算机科学和其它科学领域划清了界限，对“算法”本身给出了精确的定义，以及对于“有效运算”和可计算性的探讨，令人对“计算机”这一概念有更充分的理解。可以说整个计算机科学的理论根基都是由这一论题发展起来的，现在我们写的每一行代码、计算机上运行的每一条指令、CPU与内存之间不断交换的0和1，与其都有不可或缺的联系。