On Computable Numbers, with an Application to the Entscheidungsproblem（论可计算数及其在判定问题上的应用）

艾伦·图灵（Alan Turing）的论文《On Computable Numbers, with an Application to the Entscheidungsproblem》（论可计算数及其在判定问题上的应用）于1936年5月28日被伦敦数学学会收到，同年11月12日宣读。论文发表在该学会的《Proceedings》上，卷42，第230至265页，^[1] 据斯坦福哲学百科全书（Stanford Encyclopedia of Philosophy），这项工作是图灵独自钻研约一年后完成的，完成于1936年4月。当时他年仅23岁，是剑桥大学国王学院的研究员（Fellow）。^[2]

要解决的问题

希尔伯特（Hilbert）提出过判定问题（Entscheidungsproblem）：能否找到一种通用方法，对任何一条给定的数学命题判定它是否可以被证明。要回答这个问题，首先得把「机械地计算」说清楚。图灵的起点是一类实数，即小数展开可以被一台机器写出来的实数，他称之为可计算数。^[1]

做法

图灵描述的机器是一种抽象装置，不是某台具体的硬件。它只有有限个状态（图灵称之为m-构型，即m-configurations），读写一条被划分成方格的纸带上的符号。每一步，机器当前所处的状态，加上读写头下面的那个符号，就决定了它要写什么、向哪边移动，以及进入哪个新状态。这种装置后来被称为图灵机（Turing machine）。^[1]

图灵机看起来很简单，力量却不小。一台只有几个状态的机器，可以被设计成在纸带上反复打印0、1、0、1这样的图样；更复杂的机器则能把较长的计算拆成一个个极小的步骤逐一完成。图灵要说明的正是：凡是能按固定规则一步步进行的计算，原则上都能用这样的装置来描述。^[1]

论文中最重要的一步在第6节「通用计算机器」（The universal computing machine）。图灵证明，只要在纸带上附上所要模仿的机器的描述，一台机器就能计算任何可计算的数列。用今天的话说，这就是可编程通用计算机的思想：同一台机器装入不同的程序，就能完成不同的工作。^[1]

结果

图灵用对角线论证（diagonal argument）证明：可计算数虽然是一个很大的类，却可以排成一列、依次列出；同时，有些可以被定义的实数并不可计算。^[1]

论文的主要应用在第11节，针对的正是判定问题。图灵由此证明，判定问题不可能有解：不存在一种统一的机械方法，能对每一条数学命题判断它是否可证。^[1]

同一时期，阿隆佐·邱奇（Alonzo Church）刚提出了一个等价的概念，他称之为「有效可计算性」（effective calculability），并对判定问题得出了相似的结论。图灵在论文中提到了这一点。论文后来加入的一个附录（写于1936年8月28日）概述了证明两种概念等价的思路。^[1]

为什么重要

图灵的定义给出了「机器能算什么」的精确答案，这个答案后来成为计算机科学的基础之一。^[2] 图灵1950年的论文《计算机器与智能》（Computing Machinery and Intelligence）讨论机器能否思考，这类讨论所依赖的，正是这同一个精确的计算概念。^[2]

图灵因这项1936年的成就，于1951年当选为皇家学会会士（Fellow of the Royal Society）。^[2]

后来的影响

今天讨论计算机能做什么、不能做什么，仍然常以图灵机和通用机器作为基本框架。通用机器的思想是通用可编程计算机的基础；判定问题的否定答案，则是后来许多关于计算极限的结论的源头，例如某些问题在原则上无法被任何程序统一解决。