今天这段依然出自艾伦·图灵（Alan Turing）1936年发表的经典论文《论可计算数及其在判定问题上的应用》（Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936），具体是文章的第九章。

原文

9. The extent of the computable numbers.

No attempt has yet been made to show that the "computable" numbers include all numbers which would naturally be regarded as computable. All arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically. The real question at issue is "What are the possible processes which can be carried out in computing a number?"

The arguments which I shall use are of three kinds: (a) A direct appeal to intuition. (b) A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal). (c) Giving examples of large classes of numbers which are computable.

Once it is granted that computable numbers are all "computable" several other propositions of the same character follow. In particular, it follows that, if there is a general process for determining whether a formula of the Hilbert functional calculus is provable, then the determination can be carried out by a machine.

I. [Type (a)]. This argument is only an elaboration of the ideas presented in §1.

Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent. The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral such as 17 or 999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, indeed, attempts to have an enumerable infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.

The behaviour of the computer at any moment is determined by the symbols which he is observing, and his "state of mind" at that moment. We may suppose that there is a bound $B$ to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be "arbitrarily close" and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.

Let us imagine the operations performed by the computer to be split up into "simple operations" which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always "observed" squares.

Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within $L$ squares of an immediately previously observed square.

In connection with "immediate recognisability", it may be thought that there are other kinds of square which are immediately recognisable. In particular, squares marked by special symbols might be taken as immediately recognisable. Now if these squares are marked only by single symbols there can be only a finite number of them, and we should not upset our theory by adjoining these marked squares to the observed squares. If, on the other hand, they are marked by a sequence of symbols, we cannot regard the process of recognition as a simple process. This is a fundamental point and should be illustrated. In most mathematical papers the equations and theorems are numbered. Normally the numbers do not go beyond (say) 1000. It is, therefore, possible to recognise a theorem at a glance by its number. But if the paper was very long, we might reach Theorem 157767733443477; then, farther on in the paper, we might find "... hence (applying Theorem 157767733443477) we have...". In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure, possibly ticking the figures off in pencil to make sure of their not being counted twice. If in spite of this it is still thought that there are other "immediately recognisable" squares, it does not upset my contention so long as these squares can be found by some process of which my type of machine is capable. This idea is developed in III below.

The simple operations must therefore include: (a) Changes of the symbol on one of the observed squares. (b) Changes of one of the squares observed to another square within $L$ squares of one of the previously observed squares.

It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following: (A) A possible change (a) of symbol together with a possible change of state of mind. (B) A possible change (b) of observed squares, together with a possible change of state of mind.

The operation actually performed is determined, as has been suggested on p.250, by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation is carried out.

We may now construct a machine to do the work of this computer. To each state of mind of the computer corresponds an "m-configuration" of the machine. The machine scans $B$ squares corresponding to the $B$ squares observed by the computer. In any move the machine can change a symbol on a scanned square or can change any one of the scanned squares to another square distant not more than $L$ squares from one of the other scanned squares. The move which is done, and the succeeding configuration, are determined by the scanned symbol and the m-configuration. The machines just described do not differ very essentially from computing machines as defined in §2, and corresponding to any machine of this type a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the computer.

II. [Type (b)].

If the notation of the Hilbert functional calculus is modified so as to be systematic, and so as to involve only a finite number of symbols, it becomes possible to construct an automatic machine $\mathcal{K}$ which will find all the provable formulae of the calculus.

Now let $\alpha$ be a sequence, and let us denote by $G_\alpha(x)$ the proposition "The $x$-th figure of $\alpha$ is 1", so that $-G_\alpha(x)$ means "The $x$-th figure of $\alpha$ is 0". Suppose further that we can find a set of properties which define the sequence $\alpha$ and which can be expressed in terms of $G_\alpha(x)$ and of the propositional functions $N(x)$ meaning "$x$ is a non-negative integer" and $F(x,y)$ meaning "$y = x + 1$". When we join all these formulae together conjunctively we shall have a formula, $\mathfrak{U}$ say, which defines $\alpha$. The terms of $\mathfrak{U}$ must include the necessary parts of the Peano axioms, viz.,

$$(\exists u) N(u) \& (x)(N(x) \to (\exists y)F(x,y)) \& (F(x,y) \to N(y)),$$

which we will abbreviate to $P$.

When we say "$\mathfrak{U}$ defines $\alpha$", we mean that $-\mathfrak{U}$ is not a provable formula, and also that, for each $n$, one of the following formulae $(A_n)$ or $(B_n)$ is provable:

$$\mathfrak{U} \& F^{(n)} \to G_\alpha(u^{(n)}), \quad (A_n)$$

$$\mathfrak{U} \& F^{(n)} \to (-G_\alpha(u^{(n)})), \quad (B_n)$$

where $F^{(n)}$ stands for $F(u, u') \& F(u', u'') \& \dots F(u^{(n-1)}, u^{(n)})$.

I say that $\alpha$ is then a computable sequence: a machine $\mathcal{K}_\alpha$ to compute $\alpha$ can be obtained by a fairly simple modification of $\mathcal{K}$.

We divide the motion of $\mathcal{K}\alpha$ into sections. The $n$-th section is devoted to finding the $n$-th figure of $\alpha$. After the $(n-1)$-th section is finished a double colon :: is printed after all the symbols, and the succeeding work is done wholly on the squares to the right of this double colon. The first step is to write the letter "A" followed by the formula $(A_n)$ and then "B" followed by $(B_n)$. The machine $\mathcal{K}\alpha$ then starts to do the work of $\mathcal{K}$, but whenever a provable formula is found, this formula is compared with $(A_n)$ and with $(B_n)$. If it is the same formula as $(A_n)$, then the figure "1" is printed, and the $n$-th section is finished. If it is $(B_n)$, then "0" is printed and the section is finished. If it is different from both, then the work of $\mathcal{K}$ is continued from the point at which it had been abandoned. Sooner or later one of the formulae $(A_n)$ or $(B_n)$ is reached; this follows from our hypotheses about $\alpha$ and $\mathfrak{U}$, and the known nature of $\mathcal{K}$. Hence the $n$-th section will eventually be finished; $\mathcal{K}_\alpha$ is circle-free; $\alpha$ is computable.

It can also be shown that the numbers $\alpha$ definable in this way by the use of axioms include all the computable numbers. This is done by describing computing machines in terms of the function calculus.

It must be remembered that we have attached rather a special meaning to the phrase "$\mathfrak{U}$ defines $\alpha$". The computable numbers do not include all (in the ordinary sense) definable numbers. Let $\delta$ be a sequence whose $n$-th figure is 1 or 0 according as $n$ is or is not satisfactory. It is an immediate consequence of the theorem of §8 that $\delta$ is not computable. It is (so far as we know at present) possible that any assigned number of figures of $\delta$ can be calculated, but not by a uniform process. When sufficiently many figures of $\delta$ have been calculated, an essentially new method is necessary in order to obtain more figures.

III. This may be regarded as a modification of I or as a corollary of II.

We suppose, as in I, that the computation is carried out on a tape; but we avoid introducing the "state of mind" by considering a more physical and definite counterpart of it. It is always possible for the computer to break off from his work, to go away and forget all about it, and later to come back and go on with it. If he does this he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. This note is the counterpart of the "state of mind". We will suppose that the computer works by such a desultory manner that he never does more than one step at a sitting. The note of instructions must enable him to carry out one step and write the next note. Thus the state of progress of the computation at any stage is completely determined by the note of instructions and the symbols on the tape. That is, the state of the system may be described by a single expression (sequence of symbols), consisting of the symbols on the tape followed by $\Delta$ (which we suppose not to appear elsewhere) and then by the note of instructions. This expression may be called the "state formula". We know that the state formula at any given stage is determined by the state formula before the last step was made, and we assume that the relation of these two formulae is expressible in the functional calculus. In other words we assume that there is an axiom $\mathfrak{U}$ which expresses the rules governing the behaviour of the computer, in terms of the relation of the state formula at any stage to the state formula at the proceeding stage. If this is so, we can construct a machine to write down the successive state formulae, and hence to compute the required number.

翻译

9. 可计算数的范围

目前还没有尝试证明“可计算”数包括了所有自然被认为是可计算的数。所有能给出的论证从根本上说都必然是诉诸直觉的，因此在数学上相当不令人满意。真正的问题是：“在计算一个数的过程中，可以执行哪些可能的过程？”

本文将使用的论证有三类： (a) 直接诉诸直觉。 (b) 证明两个定义的等价性（或许新定义在直觉上更具吸引力）。 (c) 对各大类的可计算数给举出例子。

一旦承认可计算数都是“可计算的”，其他几个具有相同性质的命题也就随之而来。具体来说，如果存在一个通用过程来确定希尔伯特函数演算的公式是否可证，那么这个确定过程就可以由机器来执行。

I. [类型 (a)]. 这个论证只是 §1 中提出的观点的详述。

计算通常是在纸上书写符号来完成的。我们可以假设这张纸被划分为方格，就像算术本一样。在初等算术中，有时会利用纸张的二维特性，比如竖式计算等。但这种二维的使用是可以避免的，相信大家都会同意，纸张的二维特性并非计算的本质。因此，我假设计算是在一维的线性纸带上进行的，纸带被划分为方格。我还假设可打印的符号数量是有限的。如果允许无限多的符号，就会出现差异极小的符号。限制符号数量并不会带来严重影响，总可以用符号序列来替代单个符号。例如，像17或999999999999999这样的阿拉伯数字通常被视为单个符号。同样，在任何欧洲语言中，单词也被视为单个符号（事实上，中文拥有可枚举的大量符号）。我们认为，单一符号与复合符号的区别在于，复合符号若过长则无法一眼识别。这与经验相符：我们无法一眼区分9999999999999999和999999999999999是否相同。

计算者在任何时刻的行为由两个因素决定：他正在观察的符号，以及他那一刻的“心理状态”。我们可以假设计算者在某一时刻能够观察到的符号或方格数量存在上限 $B$。若要观察更多内容，他必须采用连续观察的方式。我们还假设需要考虑的心理状态数量是有限的。这一限制的理由与限制符号数量的理由类似：如果承认无限多的心理状态，其中一些状态将“无限接近”，难以区分。同样，这一限制并不会严重影响计算，因为通过在纸带上记录更多符号，可以避免使用过于复杂的心理状态。

让我们想象一下计算者执行的操作被分解为“简单操作”，这些操作非常基本，以至于很难以再被进一步分割。每一个这样的操作都包括由计算者和他的纸带组成的物理系统的某种变化。如果我们知道纸带上的符号序列、其中哪些被计算者观察到（可能有特定的顺序）以及计算者的心理状态，我们就知道了系统的状态。我们可以假设在一个简单操作中，至多只有一个符号被改变。任何其他的变化都可以分解为这种类型的简单变化。对于那些符号可能以这种方式改变的方格，其情况与被观察的方格相同。因此，我们可以保持通用性的情况下提出一个假设，即符号被改变的方格总是“被观察”的方格。

除了符号变化外，简单操作还必须包括观察区域的分布变化。新的被观察方格必须是计算者能够立即识别的。可以合理假设，只能是距离最近的前一个被观察方格不超过某个固定距离的方格。也就是说，每个新的被观察方格都位于某个前一个被观察方格的 $L$ 个方格范围内。

关于“立即识别性”，人们可能会认为还有其他类型的方格是可立即识别的。尤其是，被特殊符号标记的方格可能被视为可立即识别。如果这些方格仅由单个符号标记，那么它们的数量只能是有限的，我们不应通过将这些标记方格纳入观察范围来扰乱我们的理论。另一方面，如果它们是由符号序列标记的，我们就不能将识别过程视为简单过程。这是一个基本要点，需要加以说明。在大多数数学论文中，方程和定理都有编号。通常这些编号不超过（比如说）1000。因此，通过编号一眼识别出某个定理是可能的。但是，如果论文非常长，我们可能会遇到定理157767733443477；然后在论文的后文中，我们可能会发现“...因此（应用定理157767733443477）我们得到...”。为了确定哪个是相关定理，我们将不得不逐位比较这两个数字，可能还要用铅笔划掉数字以确保没有重复计数。即便如此，如果人们仍然认为存在其他“可立即识别”的方格，只要这些方格可以通过我这类机器所能执行的某种过程找到，这并不会推翻本文的论点。这一想法将在下文III中进一步阐述。

因此，简单操作必须包括： (a) 改变其中一个被观察方格上的符号。 (b) 将其中一个被观察方格变为距离其中一个先前被观察方格 $L$ 个方格内的另一个方格。

其中一些变化可能必然涉及心理状态的改变。因此，最一般的单一操作必须被视为以下之一： (A) 可能的符号变化 (a) 连同可能的心理状态变化。 (B) 可能的被观察方格变化 (b)，连同可能的心理状态变化。

具体操作（如前所述）取决于计算者当前的心理状态及其所观察到的符号。更重要的是，这两者还决定了操作完成后计算者将进入何种新的心理状态。

我们现在可以构造一台机器来完成这位计算者的工作。计算者的每一种心理状态对应机器的一个“m-构型”（状态）。机器扫描 $B$ 个方格，对应于计算者观察到的 $B$ 个方格。在任何一步移动中，机器可以改变被扫描方格上的符号，或者将任何一个被扫描的方格变为距离其中一个其他被扫描方格不超过 $L$ 个方格的另一个方格。所做的移动和随后的构型由被扫描的符号和 m-构型决定。刚刚描述的机器与 §2 中定义的计算者器没有本质区别，并且对应于任何这种类型的机器，都可以构造一台计算机器来计算相同的序列，即由计算机计算的序列。

II. [类型 (b)].

如果希尔伯特函数演算的符号经过修改使其系统化，并且只涉及有限数量的符号，那么就有可能构造一台自动机器 $\mathcal{K}$，它能找出该演算的所有可证公式。

现在令 $\alpha$ 为一个序列，我们用 $G_\alpha(x)$ 表示命题“$\alpha$ 的第 $x$ 个数字是 1”，因此 $-G_\alpha(x)$ 意味着“$\alpha$ 的第 $x$ 个数字是 0”。进一步假设我们可以找到一组定义序列 $\alpha$ 的属性，并且这些属性可以用 $G_\alpha(x)$ 以及命题函数 $N(x)$（意为“$x$ 是非负整数”）和 $F(x,y)$（意为“$y = x + 1$”）来表达。当我们把所有这些公式用合取连接起来时，我们将得到一个公式，设为 $\mathfrak{U}$，它定义了 $\alpha$。$\mathfrak{U}$ 的项必须包括皮亚诺公理的必要部分，即：

$$(\exists u) N(u) \& (x)(N(x) \to (\exists y)F(x,y)) \& (F(x,y) \to N(y)),$$

我们将此缩写为 $P$。

当我们说“$\mathfrak{U}$ 定义 $\alpha$”时，实际的意思是 $-\mathfrak{U}$ 不是一个可证公式，并且对于每个 $n$，以下公式 $(A_n)$ 或 $(B_n)$ 中必有一个是可证的：

$$\mathfrak{U} \& F^{(n)} \to G_\alpha(u^{(n)}), \quad (A_n)$$

$$\mathfrak{U} \& F^{(n)} \to (-G_\alpha(u^{(n)})), \quad (B_n)$$

其中 $F^{(n)}$ 代表 $F(u, u') \& F(u', u'') \& \dots F(u^{(n-1)}, u^{(n)})$。

称 $\alpha$ 此时是一个可计算序列：计算 $\alpha$ 的机器 $\mathcal{K}_\alpha$ 可以通过对 $\mathcal{K}$ 进行相当简单的修改而获得。

我们将 $\mathcal{K}\alpha$ 的动作分为若干段。第 $n$ 段致力于寻找 $\alpha$ 的第 $n$ 个数字。在第 $(n-1)$ 段结束后，在所有符号后面打印一个双冒号 ::，接下来的工作完全在这个双冒号右边的方格上进行。第一步是写下字母“A”后跟公式 $(A_n)$，然后是“B”后跟 $(B_n)$。机器 $\mathcal{K}\alpha$ 随后开始做 $\mathcal{K}$ 的工作，但每当找到一个可证公式时，就将该公式与 $(A_n)$ 和 $(B_n)$ 进行比较。如果是 $(A_n)$，则打印数字“1”，第 $n$ 段结束。如果是 $(B_n)$，则打印“0”并结束该段。如果与两者都不同，则从中断点继续 $\mathcal{K}$ 的工作。迟早会达到公式 $(A_n)$ 或 $(B_n)$ 之一；这由我们要关于 $\alpha$ 和 $\mathfrak{U}$ 的假设以及 $\mathcal{K}$ 的已知性质得出。因此，第 $n$ 段最终会完成；$\mathcal{K}_\alpha$ 是无循环的；$\alpha$ 是可计算的。

还可以证明，通过使用公理以这种方式定义的数 $\alpha$ 包括所有的可计算数。这可以通过用函数演算描述计算机器来完成。

要注意，我们已经赋予“$\mathfrak{U}$ 定义 $\alpha$”这个短语以相当特殊的含义。可计算数并不包括所有（在通识认知上）可定义的数。设 $\delta$ 是一个序列，其第 $n$ 个数字是 1 或 0，取决于 $n$ 是否是满意的（即无循环机器的描述数）。§8 的定理的一个直接推论是 $\delta$ 是不可计算的。但（据我们目前所知）可能 $\delta$ 的任何指定位数的数字都可以被计算出来，但不是通过一个统一的过程。当计算出足够多的 $\delta$ 的数字后，为了获得更多的数字，必须使用一种本质上新的方法。

III. 这可以看作是 I 的修改或 II 的推论。

我们像在 I 中一样假设计算是在纸带上进行的；但我们通过考虑一个更物理和确定的对应物来避免引入“心理状态”。计算者总是可以中断他的工作，离开并完全忘记它，稍后再回来继续。如果他这样做，他必须留下一张指令便条（以某种标准形式书写），解释如何继续工作。这张便条是“心理状态”的对应物。我们将假设计算者以一种断断续续的方式工作，他一次只做一步。指令便条必须能让他执行一步并写下下一张便条。因此，计算在任何阶段的进展状态完全由指令便条和纸带上的符号决定。也就是说，系统的状态可以用一个单一的表达式（符号序列）来描述，该表达式由纸带上的符号、后跟 $\Delta$（我们假设它不出现在其他地方）以及指令便条组成。这个表达式可以称为“状态公式”。我们知道，任何给定阶段的状态公式是由上一步之前的状态公式决定的，我们假设这两个公式之间的关系可以在函数演算中表达。换句话说，我们假设存在一个公理 $\mathfrak{U}$，它用任何阶段的状态公式与前一阶段的状态公式之间的关系来表达控制计算者行为的规则。如果是这样，我们可以构造一台机器来写下连续的状态公式，从而计算所需的数字。

逐段解析

1. 为什么需要哲学论证？

“目前还没有尝试证明‘可计算’数包括了所有自然被认为是可计算的数... 所有能给出的论证从根本上说都必然是诉诸直觉的...”

• 定义的鸿沟：图灵非常清醒地认识到，他正在做一件极其困难的事——定义“计算”本身。
• 直觉 vs 形式化：“可计算”这个词在日常生活中是一个模糊的直觉概念（Intuitive concept），而图灵机是一个严格的数学定义（Formal definition）。要证明这两者是等价的，不可能通过纯数学推导，只能通过说服（Persuasion），让读者相信图灵机确实捕捉到了人类计算的所有本质特征。这就是著名的 邱奇-图灵论题（Church-Turing Thesis）。

2. 对人类计算行为的解构（类型 a）

图灵像一位显微镜下的生物学家，将人类计算的过程拆解得体无完肤：

“计算通常是通过在纸上写下某些符号来完成的... 我假设计算是在一维纸上进行的...”

• 一维性：虽然我们在二维纸上算术，但本质上我们可以把二维表格拉直成一条长带子。二维只是为了方便阅读，不是计算的必要条件。

“我还将假设可以打印的符号数量是有限的。”

• 离散性：人类的感知能力是有限的。如果符号有无穷多种（比如长度精确到小数点后无数位的线段），我们就无法区分它们。为了保证计算的可重复性和确定性，符号集必须是有限且离散的。
• 中文的例子：图灵甚至幽默地提到了中文（"Chinese, indeed, attempts to have an enumerable infinity of symbols"），认为汉字虽然多，但也是试图用有限的组合去表达无限的概念（尽管实际上汉字数量也是有限的，只是很大）。

“我们无法一眼看出 9999999999999999 和 999999999999999 是否相同。”

• 局部性：这是图灵机“读写头”设计的核心依据。人类在某一瞬间的视野（Focus）是非常小的。面对长串数字，我们只能扫描（Scan）——看一部分，移动目光，再看下一部分。图灵机正是这样设计的：每次只看一个格。

3. 心理状态的有限性与机器构造

“我们还将假设需要考虑的心理状态的数量是有限的... 如果我们承认无限多的心理状态，其中一些将是‘任意接近’的，并且会被混淆。”

• 大脑作为有限状态机：这是最具唯物色彩的论断。图灵认为，在计算过程中，人脑的“状态”不能是无限连续的（像模拟信号那样），否则微小的扰动就会导致错误。为了精确计算，大脑必须处于一系列清晰、可区分的离散状态中（Digital states）。
• 外部存储的重要性：既然脑子里的状态有限，如果问题太复杂怎么办？记在纸上！这再次呼应了图灵机的设计：有限的内部控制器 + 无限的外部纸带。
• 从人到机器：既然人的计算过程被分解为有限个“心理状态”和有限种“简单操作”（写字、移动），那么我们完全可以造一台机器（图灵机），用它的“m-构型”对应人的“心理状态”，用它的读写头对应人的眼睛和笔。这样，图灵机就是人类计算者的机械化身。

4. 逻辑定义的等价性（类型 b）

这一部分展示了图灵深厚的逻辑学功底，他将“计算”与“证明”联系了起来。

• 希尔伯特演算：图灵利用了一阶逻辑（First-order logic）的通用性。
• 机器 $\mathcal{K}$：这是一台枚举所有逻辑定理的机器。只要公理系统是有限且形式化的，我们就可以通过机械搜索列出所有可证的定理。
• 定义 $\alpha$：图灵提出，如果一个数字 $\alpha$ 可以被一组公理 $\mathfrak{U}$ 唯一确定（即公理能证明 $\alpha$ 的每一位是 0 还是 1），那么 $\alpha$ 就是可计算的。
• 构造 $\mathcal{K}_\alpha$：
• 让机器 $\mathcal{K}$ 不断生成定理。
• 检查生成的定理是不是“第 $n$ 位是 0”或“第 $n$ 位是 1”的形式。
• 一旦找到，就打印出来，然后找下一位。
• 结论：“逻辑上可定义”蕴含“图灵机可计算”。这为可计算性提供了一个独立于机器的逻辑支撑，增强了定义的鲁棒性。

5. “状态公式”与物理化身（论证 III）

“计算者总是可以中断他的工作... 留下一张指令便条... 这张便条是‘心理状态’的对应物。”

• 去心理化：图灵进一步剥离了“心理状态”的神秘感。他将其比作“存档点”（Save point）或“断点续传”的记录。
• 状态公式 (State Formula)：系统的完整快照 = 纸带内容 + 指令便条。
• 离散演化：计算过程就是状态公式序列 $S_0 \to S_1 \to S_2 \dots$ 的演化。只要这个演化规则是明确的（可逻辑表达的），机器就能模拟它。这再次统一了论证 I（物理操作）和论证 II（逻辑定义）。

总结

这一章是图灵论文中哲学味最浓的一章，也是人工智能思想的源头。 1. 还原论：图灵论证了人类在计算方面的智能活动可以被还原为一系列极其简单的物理操作。 2. 物理限制：图灵考虑到了人在计算过程中的物理限制（视野有限、状态离散、区分度有限），并将这些限制编码进了图灵机的定义中。 3. 图灵论题：通过这些论证，图灵试图说服世界：凡是人脑能机械地算出来的东西，图灵机一定也能算出来。 图灵机就是人类计算行为的数学替身。