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

本章图灵建立了可计算函数的完整理论框架，证明了可计算性在复合、递归等操作下封闭，并通过可计算收敛性证明了 $\pi$、$e$ 及大量经典函数的可计算性，为可计算分析学科奠定了基础。核心创新在于将序列结构编码、形式系统推理与机器计算三种视角统一，揭示了计算的内在统一性。

原文

10. Examples of large classes of numbers which are computable.

It will be useful to begin with definitions of a computable function of an integral variable and of a computable variable, etc. There are many equivalent ways of defining a computable function of an integral variable. The simplest is, possibly, as follows. If $\gamma$ is a computable sequence in which 0 appears infinitely often, and $n$ is an integer, then let us define $\xi(\gamma, n)$ to be the number of figures 1 between the $n$-th and the $(n+1)$-th figure 0 in $\gamma$. Then $\phi(n)$ is computable if, for all $n$ and some $\gamma$, $\phi(n) = \xi(\gamma, n)$. An equivalent definition is this. Let $H(x, y)$ mean $\phi(x) = y$. Then, if we can find a contradiction-free axiom $\mathfrak{A}\phi$, such that $\mathfrak{A}\phi \to P$, and if for each integer $n$ there exists an integer $N$, such that $$ \mathfrak{A}\phi \& F^{(N)} \to H(u^{(n)}, u^{(\phi(n))}), $$ and such that, if $m \neq \phi(n)$, then, for some $N'$, $$ \mathfrak{A}\phi \& F^{(N')} \to (\neg H(u^{(n)}, u^{(m)})), $$ then $\phi$ may be said to be a computable function.

We cannot define general computable functions of a real variable, since there is no general method of describing a real number, but we can define a computable function of a computable variable. If $n$ is satisfactory, let $\gamma_n$ be the number computed by $\mathfrak{A}(n)$, and let $$ \alpha_n = \tan(\pi(\gamma_n - \frac{1}{2})) $$ unless $\gamma_n = 0$ or $\gamma_n = 1$, in either of which cases $\alpha_n = 0$. Then, as $n$ runs through the satisfactory numbers, $\alpha_n$ runs through the computable numbers. Now let $g(n)$ be a computable function which can be shown to be such that for any satisfactory argument its value is satisfactory. Then the function $f$, defined by $f(\alpha_n) = \alpha_{g(n)}$, is a computable function and all computable functions of a computable variable are expressible in this form.

Similar definitions may be given of computable functions of several variables, computable-valued functions of an integral variable, etc.

I shall enunciate a number of theorems about computability, but I shall prove only (ii) and a theorem similar to (iii).

(i) A computable function of a computable function of an integral or computable variable is computable.

(ii) Any function of an integral variable defined recursively in terms of computable functions is computable. I.e. if $\phi(m, n)$ is computable, and $r$ is some integer, then $\psi(n)$ is computable, where $$ \psi(0) = r, $$ $$ \psi(n) = \phi(n, \psi(n-1)). $$

(iii) If $f(m, n)$ is a computable function of two integral variables, then $\phi(n, n)$ is a computable function of $n$.

(iv) If $f(n)$ is a computable function whose value is always 0 or 1, then the sequence whose $n$-th figure is $f(n)$ is computable.

Dedekind's theorem does not hold in the ordinary form if we replace "real" throughout by "computable". But it holds in the following form:

(v) If $G(a)$ is a propositional function of the computable numbers and $$ (a) \quad (\exists \alpha)(\exists \beta)[G(\alpha) \& (\neg G(\beta))], $$ $$ (b) \quad G(a) \& (\neg G(\beta)) \to (a < \beta), $$ and there is a general process for determining the truth value of $G(a)$, then there is a computable number $\xi$ such that $$ G(a) \to a < \xi, $$ $$ \neg G(a) \to \xi \leq a, $$ $$ G(a) \to a \leq \xi. $$ In other words, the theorem holds for any section of the computables such that there is a general process for determining to which class a given number belongs.

Owing to this restriction of Dedekind's theorem, we cannot say that a computable bounded increasing sequence of computable numbers has a computable limit. This may possibly be understood by considering a sequence such as $$ -1, -\frac{1}{2}, -\frac{1}{4}, -\frac{1}{8}, -\frac{1}{16}, \dots $$

On the other hand, (v) enables us to prove

(vi) If $a$ and $\beta$ are computable and $a < \beta$ and $\phi(a) < 0 < \phi(\beta)$, where $\phi(x)$ is a computable increasing continuous function, then there is a unique computable number $\gamma$ satisfying $a < \gamma < \beta$ and $\phi(\gamma) = 0$.

Computable convergence.

We shall say that a sequence $\beta_n$ of computable numbers converges computably if there is a computable integral valued function $N(\epsilon)$ of the computable variable $\epsilon$, such that we can show that, if $\epsilon > 0$ and $n > N(\epsilon)$, then $|\beta_n - \beta_\infty| < \epsilon$.

We can then show that

(vii) A power series whose coefficients form a computable sequence of computable numbers is computably convergent at all computable points in the interior of its interval of convergence.

(viii) The limit of a computably convergent sequence is computable.

And with the obvious definition of "uniformly computably convergent":

(ix) The limit of a uniformly computably convergent computable sequence of computable functions is a computable function. Hence

(x) The sum of a power series whose coefficients form a computable sequence is a computable function in the interior of its interval of convergence.

From (vii) and $\pi = 4(1 - \frac{1}{3} + \frac{1}{5} - \dots)$ we deduce that $\pi$ is computable. From $e = 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \dots$ we deduce that $e$ is computable. From (vi) we deduce that all real algebraic numbers are computable. From (vi) and (x) we deduce that the real zeros of the Bessel functions are computable.

Proof of (ii).

Let $M(x, y)$ mean "$\psi(x) = y$", and let $K(x, y, z)$ mean "$\phi(x, y) = z$". $\mathfrak{A}\psi$ is the axiom for $\phi(x, y)$. We take $\mathfrak{A}\psi$ to be $$ \mathfrak{A}_\phi \& P \& (F(x, y) \to G(x, y)) \& (G(y, z) \& G(y, z') \to G(z, z')) $$ $$ \& [F^{(M)} \to M(u^{(M)}, u^{(M')}) \& (F(M, u, z) \& M(u, z, z) \to M(u^{(z)}, z)] $$ $$ \& [M(u, z) \& G(z, t) \Rightarrow G(t, z) \to (\neg M(u, z))]. $$

I shall not give the proof of consistency of $\mathfrak{A}_\psi$. Such a proof may be constructed by the methods used in Hilbert and Bernays, Grundlagen der Mathematik (Berlin, 1934), p. 209 et seq. The consistency is also clear from the meaning.

Suppose that, for some $n$, $N$, we have shown $$ \mathfrak{A}\psi \& F^{(N)} \to M(u^{(n-1)}, u^{(m-1)}), $$ then, for some $M$, $$ \mathfrak{A}\psi \& F^{(M)} \to G(u^{(n-1)}, u^{(m-1)}, u^{(m(n-1))}) $$ $$ \mathfrak{A}\psi \& F^{(M')} \to F(u^{(n-1)}, u^{(m(n-1))}, u^{(m)}) \& M(u^{(m(n-1))}, u^{(m-1)}) $$ $$ \& K(u^{(m)}, u^{(m-1)}, u^{(m)}) $$ $$ \mathfrak{A}\psi \& F^{(M')} \to M(u^{(m)}, u^{(m)}). $$ Hence $$ \mathfrak{A}_\psi \& F^{(M')} \to M(u^{(m)}, u^{(m)}). $$ Also

Hence for each $m$ some formula of the form $$ \mathfrak{A}\psi \& F^{(M)} \to M(u^{(m)}, u^{(m)}) $$ is provable. Also, if $M' \geq M$ and $M' \geq m$ and $\psi(n)$, then $$ \mathfrak{A}\psi \& F^{(M')} \to G(u^{(m)}, u^{(m')}, u^{(m)}) \to G(u^{(m')}, u^{(m')}) $$ and $$ \mathfrak{A}\psi \& F^{(M')} \to [(G(u^{(m)}, u^{(m')}) \to G(u^{(m')}, u^{(m)})) $$ $$ \& H(u^{(m')}, u^{(m-1)}, u^{(m')}) $$ $$ \to (\neg(M(u^{(m')}, u^{(m)})))]. $$ Hence $$ \mathfrak{A}\psi \& F^{(M')} \to (\neg M(u^{(m')}, u^{(m)})). $$

The conditions of our second definition of a computable function are therefore satisfied. Consequently $\psi$ is a computable function.

Proof of a modified form of (iii).

Suppose that we are given a machine $\mathfrak{N}$, which, starting with a tape bearing on it $\varepsilon$ followed by a sequence of any number of letters "F" on $F$-squares and in the $m$-configuration $b$, will compute a sequence $\gamma_n$ depending on the number $n$ of letters "F". If $M_n$ is the $n$-th figure of $\gamma_n$, then the sequence whose $n$-th figure is $M_n$ is computable.

We suppose that the table for $\mathfrak{U}$ has been written out in such a way that in each line only one operation appears in the operations column. We also suppose that $\Xi$, $\Theta$, $\overline{0}$, and $\overline{1}$ do not occur in the table, and we replace $\circ$ throughout by $\Theta$, $0$ by $\overline{0}$, and $1$ by $\overline{1}$. Further substitutions are then made. Any line of form

$$ \begin{array}{cccc} \mathfrak{U} & a & P\overline{0} & \mathfrak{B} \end{array} $$

we replace by

$$ \begin{array}{cccc} \mathfrak{U} & a & P\overline{0} & \mathrm{re}(\mathfrak{B}, u, h, k) \end{array} $$

and any line of the form

$$ \begin{array}{cccc} \mathfrak{U} & a & P\overline{1} & \mathfrak{B} \end{array} $$

by

$$ \begin{array}{cccc} \mathfrak{U} & a & P\overline{1} & \mathrm{re}(\mathfrak{B}, v, h, k) \end{array} $$

and we add to the table the following lines:

$$ \begin{array}{ccc} u & & \mathrm{pe}(u_1, 0) \ u_1 & R, Pk, R, P\Theta, R, P\Theta & u_2 \ u_2 & & \mathrm{re}(u_3, u_2, k, h) \ u_3 & & \mathrm{pe}(u_2, F) \end{array} $$

and similar lines with $v$ for $u$ and $1$ for $0$ together with the following line

$$ \begin{array}{ccc} c & R, P\Xi, R, Ph & b. \end{array} $$

We then have the table for the machine $\mathfrak{U}'$ which computes $\beta$.
The initial $m$-configuration is $c$, and the initial scanned symbol is the second $a$.

翻译

10. 可计算数按类举例

首先，有必要定义整数变量的可计算函数和可计算变量等。定义整数变量的可计算函数有许多等价的方法。最简单的可能是如下定义：如果 $\gamma$ 是一个可计算序列，其中0无限次经常出现，且 $n$ 是一个整数，那么令 $\xi(\gamma, n)$ 为 $\gamma$ 中第 $n$ 个和第 $(n+1)$ 个0之间1的个数。那么如果对于所有 $n$ 和某些 $\gamma$，$\phi(n) = \xi(\gamma, n)$，则 $\phi(n)$ 是可计算的。一个等价的定义是：令 $H(x, y)$ 表示 $\phi(x) = y$。那么，如果我们能找到一个相容的公理 $\mathfrak{A}\phi$，使得 $\mathfrak{A}\phi \to P$，且对于每个整数 $n$ 存在整数 $N$，使得

$$ \mathfrak{A}_\phi \& F^{(N)} \to H(u^{(n)}, u^{(\phi(n))}), $$

而且，如果 $m \neq \phi(n)$，则对于某个 $N'$，

$$ \mathfrak{A}_\phi \& F^{(N')} \to (\neg H(u^{(n)}, u^{(m)})), $$

则可以说 $\phi$ 是一个可计算函数。

我们无法定义实变量的一般可计算函数，因为没有描述实数的一般方法，但我们可以定义可计算变量的可计算函数。如果 $n$ 是满意数，令 $\gamma_n$ 为 $\mathfrak{A}(n)$ 计算出的数，并令

$$ \alpha_n = \tan(\pi(\gamma_n - \frac{1}{2})) $$

但 $\gamma_n = 0$ 或 $\gamma_n = 1$ 这两种情形除外，此时 $\alpha_n = 0$。当 $n$ 遍历所有满意数时，$\alpha_n$ 遍历所有可计算数。现设 $g(n)$ 为一可计算函数，且可证明：对其任意满意参数，函数值亦为满意数。则由 $f(\alpha_n) = \alpha_{g(n)}$ 定义的函数 $f$ 是可计算函数，且可计算变量的所有可计算函数皆可表示为此种形式。

对于多变量可计算函数、整数变量的可计算值函数等，也可以给出类似定义。

本文将阐述一些关于可计算性的定理，但只证明(ii)和一个类似于(iii)的定理。

(i) 整数或可计算变量的可计算函数的可计算函数是可计算的。

(ii) 以可计算函数递归定义的整数变量的任何函数都是可计算的。即如果 $\phi(m, n)$ 是可计算的，且 $r$ 是某个整数，则 $\psi(n)$ 是可计算的，其中 $$ \psi(0) = r, $$ $$ \psi(n) = \phi(n, \psi(n-1)). $$

(iii) 如果 $f(m, n)$ 是有两个整数变量的可计算函数，则 $\phi(n, n)$ 是 $n$ 的可计算函数。

(iv) 如果 $f(n)$ 是一个值总是0或1的可计算函数，则第 $n$ 位数字为 $f(n)$ 的序列是可计算的。

如果我们将"实数"替换为"可计算数"，戴德金定理在通常形式下不成立。但它以以下形式成立：

(v) 如果 $G(a)$ 是可计算数的命题函数，且 $$ (a) \quad (\exists \alpha)(\exists \beta)[G(\alpha) \& (\neg G(\beta))], $$ $$ (b) \quad G(a) \& (\neg G(\beta)) \to (a < \beta), $$

且存在确定 $G(a)$ 真值的一般过程，则存在一个可计算数 $\xi$ 使得

$$ G(a) \to a < \xi, $$ $$ \neg G(a) \to \xi \leq a, $$ $$ G(a) \to a \leq \xi. $$

换句话说，该定理对可计算数的任何分割都成立，只要存在确定给定数属于哪个类的一般过程。

由于戴德金定理的这个限制，我们不能说可计算数的有界递增可计算序列具有可计算极限。这可以通过考虑如下序列来理解：

$$ -1, -\frac{1}{2}, -\frac{1}{4}, -\frac{1}{8}, -\frac{1}{16}, \dots $$

另一方面，(v)使我们能够证明

(vi) 如果 $a$ 和 $\beta$ 是可计算的且 $a < \beta$ 且 $\phi(a) < 0 < \phi(\beta)$，其中 $\phi(x)$ 是可计算的递增连续函数，则存在唯一的可计算数 $\gamma$ 满足 $a < \gamma < \beta$ 且 $\phi(\gamma) = 0$。

可计算收敛性。

我们说可计算数的序列 $\beta_n$ 可计算收敛，如果存在可计算变量 $\epsilon$ 的可计算整数值函数 $N(\epsilon)$，使得我们可以证明，如果 $\epsilon > 0$ 且 $n > N(\epsilon)$，则 $|\beta_n - \beta_\infty| < \epsilon$。

然后我们可以证明

(vii) 系数形成可计算数的可计算序列的幂级数在其收敛区间的内部所有可计算点处可计算收敛。

(viii) 可计算收敛序列的极限是可计算的。

以及明显定义的"一致可计算收敛"：

(ix) 可计算函数的一致可计算收敛可计算序列的极限是可计算函数。因此

(x) 系数形成可计算序列的幂级数的和在其收敛区间的内部是可计算函数。

从(vii)和 $\pi = 4(1 - \frac{1}{3} + \frac{1}{5} - \dots)$ 我们推导出 $\pi$ 是可计算的。 从 $e = 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \dots$ 我们推导出 $e$ 是可计算的。 从(vi)我们推导出所有实代数数都是可计算的。 从(vi)和(x)我们推导出贝塞尔函数的实零点是可计算的。

(ii)的证明。

令 $M(x, y)$ 表示"$\psi(x) = y$"，令 $K(x, y, z)$ 表示"$\phi(x, y) = z$"。$\mathfrak{A}\psi$ 是 $\phi(x, y)$ 的公理。我们取 $\mathfrak{A}\psi$ 为 $$ \mathfrak{A}_\phi \& P \& (F(x, y) \to G(x, y)) \& (G(y, z) \& G(y, z') \to G(z, z')) $$ $$ \& [F^{(M)} \to M(u^{(M)}, u^{(M')}) \& (F(M, u, z) \& M(u, z, z) \to M(u^{(z)}, z)] $$ $$ \& [M(u, z) \& G(z, t) \Rightarrow G(t, z) \to (\neg M(u, z))]. $$

我不会给出 $\mathfrak{A}_\psi$ 的一致性证明。这样的证明可以用希尔伯特和贝尔奈斯《数学基础》(柏林，1934年，第209页及以后)中使用的方法构造。从意义上来说一致性也很清楚。

假设对于某些 $n$, $N$，我们已经证明了 $$ \mathfrak{A}\psi \& F^{(N)} \to M(u^{(n-1)}, u^{(m-1)}), $$ 那么，对于某个 $M$， $$ \mathfrak{A}\psi \& F^{(M)} \to G(u^{(n-1)}, u^{(m-1)}, u^{(m(n-1))}) $$ $$ \mathfrak{A}\psi \& F^{(M')} \to F(u^{(n-1)}, u^{(m(n-1))}, u^{(m)}) \& M(u^{(m(n-1))}, u^{(m-1)}) $$ $$ \& K(u^{(m)}, u^{(m-1)}, u^{(m)}) $$ $$ \mathfrak{A}\psi \& F^{(M')} \to M(u^{(m)}, u^{(m)}). $$ 因此 $$ \mathfrak{A}_\psi \& F^{(M')} \to M(u^{(m)}, u^{(m)}). $$ 同样

因此对于每个 $m$，某些形式为 $$ \mathfrak{A}\psi \& F^{(M)} \to M(u^{(m)}, u^{(m)}) $$ 的公式是可证明的。此外，如果 $M' \geq M$ 且 $M' \geq m$ 且 $\psi(n)$，则 $$ \mathfrak{A}\psi \& F^{(M')} \to G(u^{(m)}, u^{(m')}, u^{(m)}) \to G(u^{(m')}, u^{(m')}) $$ 且 $$ \mathfrak{A}\psi \& F^{(M')} \to [(G(u^{(m)}, u^{(m')}) \to G(u^{(m')}, u^{(m)})) $$ $$ \& H(u^{(m')}, u^{(m-1)}, u^{(m')}) $$ $$ \to (\neg(M(u^{(m')}, u^{(m)})))]. $$ 因此 $$ \mathfrak{A}\psi \& F^{(M')} \to (\neg M(u^{(m')}, u^{(m)})). $$

因此满足了我们可计算函数第二个定义的条件。因此 $\psi$ 是一个可计算函数。

(iii)修改形式的证明。

假设给我们一台机器 $\mathfrak{N}$，它从带有 $\varepsilon$ 的磁带开始，后面跟着任意数量的字母"F"在 $F$ 方格上，且处于 $m$ 配置 $b$ 中，将计算依赖于字母"F"数量 $n$ 的序列 $\gamma_n$。如果 $M_n$ 是 $\gamma_n$ 的第 $n$ 个数字，则第 $n$ 个数字为 $M_n$ 的序列是可计算的。

我们假设 $\mathfrak{N}$ 的表格已经写出，但在此表格中字母 $u, v, w, x, y, z$ 不出现。我们也假设 $\mathfrak{N}$ 有一个最终配置 $c$，且在此配置中机器正在扫描空白方格且不执行任何操作。我们将所有地方的 $c$ 替换为 $q$ 并添加一个新的配置 $c$。$\mathfrak{N}$ 表格中的任何形式为

的行被替换为

并且我们在表格中添加以下行：

以及用 $u$ 替换 $x$ 和用1替换 $\theta$ 的类似行，再加上以下行

这样我们就得到了计算 $\beta$ 的机器 $\mathfrak{U}'$ 的表格。其初始 $m$ 配置为 $c$，初始扫描符号为第二个 $a$。

逐段解析

一、可计算函数的两种等价定义

图灵在本章开篇给出了整数变量可计算函数的两种定义。初看之下，这两种定义似乎毫不相干，但图灵证明了它们的等价性。理解这两种定义的等价性，对于深入把握可计算性的本质至关重要。

第一种定义基于序列编码。

设想有一条无限延伸的纸带，上面写着一串由0和1组成的序列。假设这个序列是可计算的，也就是说，存在一台图灵机能够逐位输出这个序列。进一步假设序列中0出现的次数是无限的。现在我们定义一个函数 $\phi$，它的第 $n$ 个函数值等于序列中第 $n$ 个0与第 $(n+1)$ 个0之间1的个数。

举一个具体的例子。假设可计算序列为 $$\gamma = 10110101110...$$

在这个序列中，我们标记出每个0的位置： $$1\underline{0}11\underline{0}1\underline{0}111\underline{0}...$$

现在数一数相邻两个0之间有多少个1： - 第1个0与第2个0之间有2个1，所以 $\phi(1) = 2$ - 第2个0与第3个0之间有1个1，所以 $\phi(2) = 1$ - 第3个0与第4个0之间有3个1，所以 $\phi(3) = 3$

这个定义的精妙之处在于，它将函数值"编码"在序列的结构中。只要图灵机能生成这个序列，我们就能从中提取出任意一点的函数值。

这里蕴含着一个深刻的思想：通过在二进制序列的结构中编码额外信息，可以从中提取出更高阶的信息。

表面上看，一条由0和1组成的序列似乎只携带了最基本的信息——每个位置是0还是1。然而图灵的编码方式揭示了一个事实：序列的内部结构本身可以编码更丰富的内容。在这个例子中，函数值并不是直接写在序列的某个位置上，而是隐藏在序列的"间隔结构"中——两个相邻的0之间有多少个1，这个数字本身就是一条额外信息。

这种编码方式可以类比为现代数据压缩技术。在Huffman编码中，字符的频率信息被编码到变长码字的结构中；在游程编码中，连续相同字符的个数被直接记录。图灵的编码与之类似，但更进一步：它不是将已知的函数值存储起来，而是展示了如何将函数的可计算性与序列的可计算性等同起来。换句话说，一个函数是可计算的，当且仅当它的值可以被编码到一个可计算序列的结构中。

更一般地说，这种"结构编码"思想暗示了计算的不同层次。在第一层，我们有原始的符号序列。在第二层，我们从序列的结构中提取出函数值。如果愿意，我们还可以继续深入：从函数值序列的结构中，再提取出更高阶的函数。这种层次化的信息提取，与后来发展出的"计算复杂性"和"信息论"有着深刻的联系。

第二种定义基于形式系统。

这个定义更加抽象，但它揭示了可计算性与数理逻辑之间的深刻联系。图灵的思路是，如果一个函数是可计算的，那么必定存在一套形式化的公理系统，能够从公理出发，通过逻辑推理，证明函数在每一点的取值。

具体来说，设 $H(x,y)$ 是一个谓词，其含义为"$\phi(x) = y$"。图灵声称，函数 $\phi$ 可计算当且仅当存在一套一致公理 $\mathfrak{A}_\phi$，满足两个条件。第一，对于任意整数 $n$，能够从公理推出 $H(n, \phi(n))$，也就是正确断言函数值。第二，对于任意 $m \neq \phi(n)$，能够推出 $\neg H(n, m)$，也就是排除所有错误的函数值。

这种定义方式与希尔伯特纲领的精神一脉相承。希尔伯特曾设想，数学真理应当能够通过有限步骤的形式推理来确证。图灵的定义暗示，可计算性同样具有这种形式化特征。当然，哥德尔的不完备性定理已经表明希尔伯特的宏大计划无法完全实现，而图灵的定义恰恰利用了形式系统的这一特性来刻画可计算性。

这两种定义的等价性并非显而易见。第一种定义是构造性的，直接给出了从序列到函数的转换方法。第二种定义则是描述性的，诉诸形式系统的推理能力。图灵证明它们等价的关键在于展示了如何从一种视角转换到另一种视角，这种转换本身就蕴含着深刻的数学洞察。

二、可计算变量的可计算函数

定义了整数变量的可计算函数后，图灵自然地想要扩展到实变量。然而这里出现了一个根本性的困难：实数无法一般性地描述。绝大多数实数是不可计算的，也就是说，不存在任何有限的方法能完整地刻画它们。既然无法"描述"一个任意的实数，自然也就无法定义以任意实数为输入的函数。

图灵的解决方案是引入"可计算变量"的概念。既然实数不可处理，那就只处理那些可计算的实数。具体做法是，每个可计算数都用一个"满意数"来编号。回忆前面的定义，满意数是那些能够正确编码一台图灵机的自然数。给定一个满意数 $n$，机器 $\mathfrak{A}(n)$ 就能计算出一个可计算数 $\gamma_n$。

但这带来一个技术问题：可计算数是 $(0,1)$ 区间的实数，而我们希望定义的函数可能以任意实数为变量。图灵巧妙地运用了三角函数来解决这个问题。

三角映射的构造与直观

图灵使用的变换是 $$\alpha_n = \tan\left(\pi\left(\gamma_n - \frac{1}{2}\right)\right)$$

让我们仔细分析这个变换是如何工作的。首先，$\gamma_n$ 是一个介于0和1之间的可计算数。当 $\gamma_n$ 取值 $\frac{1}{2}$ 时，括号内的值正好是0，于是 $\alpha_n = \tan(0) = 0$。这给出了一个自然的"原点"。

当 $\gamma_n$ 从 $\frac{1}{2}$ 向0趋近时，$\pi(\gamma_n - \frac{1}{2})$ 从0向 $-\frac{\pi}{2}$ 趋近。注意 $\tan(x)$ 在 $x$ 趋近于 $-\frac{\pi}{2}$ 时趋向负无穷。因此，当 $\gamma_n$ 趋近于0时，$\alpha_n$ 趋近于负无穷。

类似地，当 $\gamma_n$ 从 $\frac{1}{2}$ 向1趋近时，$\pi(\gamma_n - \frac{1}{2})$ 从0向 $\frac{\pi}{2}$ 趋近，而 $\tan(x)$ 在 $x$ 趋近于 $\frac{\pi}{2}$ 时趋向正无穷。因此，当 $\gamma_n$ 趋近于1时，$\alpha_n$ 趋近于正无穷。

举几个具体的数值例子： - 若 $\gamma_n = \frac{1}{2}$，则 $\alpha_n = \tan(0) = 0$ - 若 $\gamma_n = \frac{1}{4}$，则 $\alpha_n = \tan(-\frac{\pi}{4}) = -1$ - 若 $\gamma_n = \frac{3}{4}$，则 $\alpha_n = \tan(\frac{\pi}{4}) = 1$ - 若 $\gamma_n = \frac{1}{6}$，则 $\alpha_n = \tan(-\frac{\pi}{3}) = -\sqrt{3} \approx -1.732$ - 若 $\gamma_n = \frac{5}{6}$，则 $\alpha_n = \tan(\frac{\pi}{3}) = \sqrt{3} \approx 1.732$

这个变换的关键性质是它建立了一个双射：$(0,1)$ 区间内的每个可计算数都唯一对应一个实数轴上的可计算数，反之亦然。而且，这个变换本身是可计算的——给定 $\gamma_n$ 的任意精度近似，我们都能计算出 $\alpha_n$ 的相应精度近似。

可计算函数的定义

现在，如何定义一个以可计算数为变量的可计算函数呢？图灵的方法是，通过操作"索引"来间接操作实数。设 $g(n)$ 是一个整数到整数的可计算函数，它将满意数映射到满意数。那么函数 $$f(\alpha_n) = \alpha_{g(n)}$$

就定义了一个可计算变量的可计算函数。这种定义方式类似于在计算机程序中通过指针或引用来操作数据——我们不直接操作数据本身，而是操作指向数据的地址。

三、十项定理概览

图灵列举了十条关于可计算性的定理，构成了一个完整的理论框架。

定理至比较直观。定理说的是可计算函数的复合仍然是可计算的。定理涉及递归定义，证明了递归不会突破可计算性的边界。定理处理对角线情况，预示了后来的对角线引理。定理建立了可计算集合与可计算函数的联系。

定理是戴德金定理的可计算版本。经典戴德金分割定理断言实数的每个分割都确定一个实数，但在可计算世界中，还需要额外条件：必须存在算法判断一个数属于分割的哪一边。这个限制揭示了可计算分析与经典分析的本质区别——存在性不等于可构造性。定理是可计算版本的中间值定理，其重要应用是证明了所有实代数数都是可计算的。

四、可计算收敛性与重要常数的可计算性

定理至涉及可计算收敛性，这是本章最重要的内容之一。

什么是可计算收敛？

一个序列收敛，我们知道它的极限存在。但可计算收敛要求更多：我们不仅要知道序列收敛，还要知道它收敛得有多快，而且这个"收敛速度"本身必须是可计算的。

形式化地说，序列 $\beta_n$ 可计算收敛，意味着存在一个可计算函数 $N(\epsilon)$，告诉我们：为了达到精度 $\epsilon$，只需要计算序列的前 $N(\epsilon)$ 项就够了。换句话说，只要 $n > N(\epsilon)$，就有 $|\beta_n - \beta_\infty| < \epsilon$。

这个要求看起来技术性很强，但它的含义是深刻的。经典分析中，许多存在性证明只告诉我们极限存在，却无法告诉我们如何找到它。可计算收敛则要求我们有一个"有效的停止准则"：计算多少项之后，我们就可以确信结果已经达到了所需的精度。

圆周率 $\pi$ 是可计算的

图灵从定理出发，证明了圆周率 $\pi$ 是可计算的。证明的关键是莱布尼茨级数： $$\pi = 4\left(1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \cdots\right)$$

这个级数收敛较慢，但我们可以精确控制其收敛速度。级数的通项是 $(-1)^n \frac{1}{2n+1}$，系数构成可计算序列。更重要的是，这是一个交错级数，其误差不超过第一个被舍去的项的绝对值。因此，要计算 $\pi$ 到精度 $\epsilon$，只需要取前 $N$ 项使得 $\frac{4}{2N+1} < \epsilon$，即 $N > \frac{2}{\epsilon} - \frac{1}{2}$。

这意味着收敛速度的函数 $N(\epsilon) = \lceil \frac{2}{\epsilon} \rceil$ 是可计算的。给定任意精度要求，我们都能有效确定需要计算多少项。因此 $\pi$ 是可计算数。

当然，实际计算 $\pi$ 时我们会使用收敛更快的公式，比如马青公式或其他级数。但图灵的论证不需要最优算法，只需要证明存在某种有效的计算方法。

马青公式与更高效的 $\pi$ 计算方法

莱布尼茨级数虽然形式优美，但收敛速度确实太慢了。要计算 $\pi$ 到小数点后 $d$ 位，大约需要 $10^d$ 项。这在实际计算中显然不可行。

1706年，英国数学家约翰·马青发现了一个重要的公式，后人称之为马青公式： $$\frac{\pi}{4} = 4\arctan\frac{1}{5} - \arctan\frac{1}{239}$$

这个公式的精妙之处在于，它将 $\pi$ 表示为两个反正切函数的线性组合。而反正切函数可以用泰勒级数展开： $$\arctan x = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + \cdots$$

当 $x$ 较小时，这个级数收敛得非常快。在马青公式中，$\frac{1}{5}$ 和 $\frac{1}{239}$ 都是很小的数，因此两个级数都快速收敛。具体来说，计算 $\arctan\frac{1}{5}$ 时，每增加一项大约贡献 $\frac{1}{5}$ 倍的精度；计算 $\arctan\frac{1}{239}$ 时，每项贡献大约 $\frac{1}{239}$ 倍的精度。相比之下，莱布尼茨级数的各项贡献以 $\frac{1}{2n+1}$ 的速度递减，收敛慢得多。

举一个具体的数值例子。用马青公式计算 $\pi$ 到10位小数，只需要计算每个级数的前几项： - $\arctan\frac{1}{5}$ 取前8项：$0.1973955598...$ - $\arctan\frac{1}{239}$ 取前3项：$0.0041840760...$ - 代入马青公式：$\frac{\pi}{4} = 4 \times 0.1973955598 - 0.0041840760 = 0.7853981634...$ - 于是 $\pi \approx 3.1415926536...$

这个结果与 $\pi$ 的真值吻合到第10位。

马青公式的另一个优势是，它可以进一步推广。高斯发现了更一般的公式： $$\frac{\pi}{4} = 12\arctan\frac{1}{18} + 8\arctan\frac{1}{57} - 5\arctan\frac{1}{239}$$

现代计算机计算 $\pi$ 时，通常使用一类称为"查德诺夫斯基算法"的方法，其收敛速度是二次的，即每迭代一次，有效位数大约翻倍。这类算法可以在很短时间内计算出 $\pi$ 的数十万亿位。

但无论使用哪种方法，核心思想都是一样的：找到一个由可计算系数组成的级数，证明其收敛速度可计算，从而断言 $\pi$ 是可计算数。图灵的莱布尼茨级数论证是最简单的一种，虽然不是最实用的，但它完整地展示了可计算性证明的核心逻辑。

自然对数底 $e$ 是可计算的

图灵同样证明了自然对数底 $e$ 是可计算的。证明使用 $e$ 的级数定义： $$e = \sum_{k=0}^{\infty} \frac{1}{k!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \cdots$$

这个级数的通项是 $\frac{1}{k!}$，系数构成可计算序列。为了确定收敛速度，我们注意到这个级数的余项满足： $$\sum_{k=n+1}^{\infty} \frac{1}{k!} < \frac{1}{n \cdot n!}$$

因此，要计算 $e$ 到精度 $\epsilon$，只需要取前 $N$ 项使得 $\frac{1}{N \cdot N!} < \epsilon$。由于阶乘增长极快，这个条件很容易满足，而且我们可以有效计算出最小的 $N$。

幂级数与经典函数的可计算性

定理至将上述思想推广到幂级数。图灵证明，如果一个幂级数的系数构成可计算序列，那么在其收敛区间的内部，这个幂级数定义的是一个可计算函数。

这一结果的推论是巨大的。三角函数 $\sin x$、$\cos x$，指数函数 $e^x$，双曲函数 $\sinh x$、$\cosh x$，对数函数 $\ln(1+x)$，乃至贝塞尔函数等特殊函数，都可以用幂级数定义。由于它们的系数构成可计算序列，且收敛区间是可确定的，因此这些经典函数都是可计算函数。

更进一步，贝塞尔函数的实零点也是可计算的。这是因为贝塞尔函数是连续函数，我们可以用二分法在其零点附近逼近。由于贝塞尔函数的值可以通过幂级数有效计算，这个逼近过程是可计算的。

为什么这些结果重要？

图灵在这一章不仅定义了什么是可计算的，更重要的是证明了数学中绝大多数"有用的"对象——从基本的 $\pi$ 和 $e$，到三角函数、指数函数，再到代数数、超越数——都是可计算的。这极大地增强了人们对计算模型的信心。如果图灵机连 $\pi$ 都无法计算，那它作为通用计算模型就会受到质疑。但图灵证明了，我们日常用到的几乎所有数学对象都在可计算的范围之内。

当然，不可计算数确实存在，图灵在前面的章节已经通过対角线论证证明了这一点。但那些不可计算数在我们的常规数学实践中很少出现。我们日常遇到的数，几乎都是可计算的。这揭示了可计算性理论的一个重要特点：它界定了计算的边界，但这个边界在我们的日常经验中是难以触及的。