论可计算数及其在判定问题上的应用
图灵设想出最简单的机器——一个在纸带上读写的读写头——以此定义了「计算」本身，并证明：有些问题，任何机器都永远无法回答。
在任何计算机出现之前，图灵就描述了一台「能算一切」的最简单的机器——并用它证明：有些问题，任何计算机都永远无法回答。
把这个想法拆开看
想象一条长长的纸带，分成一个个方格；一个小小的读写头，一次能读、写一个方格；外加一本薄薄的规则手册。每条规则都说：若你处在某某状态、读到某某符号，就写下这个、向左或向右挪一格、并切换到那个状态。整台机器，就这么多。图灵的论断令人吃惊：凡是能用一套确定程序算出来的，都能由这样一台简单的机器做到。
接着是神来之笔。任何机器的规则手册，本身也能写成一串符号——于是它能被写到一条纸带上，喂给另一台机器。图灵造出一台「通用」机：它读入对任何别的机器的描述，然后表现得与那台机器一模一样。这就是软件：同一台设备，全看你装入哪一份描述，便成了文字处理器、计算器，或一个游戏。这一切，他在世人造出第一台之前十年就已设想出来。
它从哪里来
1935 年，22 岁的图灵——剑桥国王学院的一名研究员——旁听了马克斯·纽曼关于数理逻辑诸多未决问题的讲课。其中之一，便是希尔伯特的判定问题：它要找一套机械程序，能对任意一个数学命题，判定它是否由公理推得。图灵把「机械」二字当了真：要回答它，他得先把「机器究竟能做什么」说清楚。
他在 1936 年完成论文——随后得知，美国逻辑学家阿隆佐·邱奇刚用一套全然不同的方法得到了同样的结论。图灵的工作是独立的，且已在付印；他补上一篇附录，证明两条进路彼此吻合，不久便动身去普林斯顿，师从邱奇。他证明的核心意象——一个人被简化为一名不知疲倦、只照规则办事的抄写员——在不到十五年里，就变成了他当初只在头脑里想象的那台真机器。
它为何重要
它一举做成了两件相反的事。它为「机器之所能」划下一道清晰的界：证明某些再清楚不过的问题——比如「这个程序会不会停下来？」——并没有一个通用的机械答案，于是「把数学完全自动化」的梦想，根本不可能。而就在同一笔之下，它描述了那台通用机：证明了一台通用设备，原则上可以运行任何程序。每一台计算机，都是这一个想法的实现；它的界限与它的伟力，是在同一篇论文里、被一同发现的。
一个类比
想象一位书记员坐在桌前，面前是一条没有尽头的纸带，手边是一本薄薄的规则手册。他并不理解题目；他只是读眼前这一格、查出对得上的那条规则、写一笔、往旁边挪一格，然后重复。现在请注意：规则手册本身，也不过是写出来的字。于是你大可把「任何另一位书记员的规则手册」递给他，请他照着模仿——一位书记员，便能顶替所有人。那个无解的问题，无非是：「给定一位书记员和他的起始页，他到底会不会有放下铅笔的一刻？」没有哪本手册能永远答得出。试试下面这台小机器——它走 14 步就停，可它的同类，也许会永远跑下去。
它落在何处
这是本馆「信息」叙事的拱心石。乔治·布尔（1854）把逻辑变成了代数；库尔特·哥德尔（1931）证明了：没有任何形式系统能证明关于算术的全部真理——而图灵的机器，把这条界限改写成人人都能想象的样子。他的通用机，正是冯·诺伊曼 1945 年报告变成真硬件的那张蓝图；而它来回搬运的那个「比特」，正是香农（1948）学会去度量的东西。十四年后，图灵自己的 1950 年论文追问了续篇：不是这些机器不能做什么，而是它们究竟能否思考。
开篇 · 可计算数
The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.
§1–§2 · 计算机器
§6 · 通用计算机器
It is possible to invent a single machine which can be used to compute any computable sequence.
§11 · 判定问题
There can be no general process for determining whether a given formula U of the functional calculus K is provable.