我向您展示 1936 年艾伦·图灵 (Alan Turing) 文章《论可计算数与解决问题的应用》第一页的译文。第一章包含对计算机的描述，后来成为现代计算的基础。
这篇文章的完整翻译和解释可以在美国普及者 Charles Petzold 的著作《阅读图灵：图灵关于可计算性和图灵机的历史文章的旅程》（ISBN 978-5-97060-231-7, 978-0-470-22905-7）中阅读。
原文：
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
论可计算数及其在解决问题中的应用
图灵
[1936 年 5 月 28 日收稿 – 1936 年 11 月 12 日阅读]
“可计算”数可以简单地描述为实数，其小数形式的表达可以通过有限多种方式计算。尽管乍一看本文将数字视为可计算的，但定义和探索整数变量、实数变量、可计算变量、可计算谓词等的可计算函数几乎同样容易。然而，与这些可计算对象相关的基本问题在每种情况下都是相同的。为了详细考虑，我选择可计算数字作为可计算对象，因为考虑它们的方法是最不麻烦的。我希望尽快描述可计算数与可计算函数的关系等等。同时，将在以可计算数表示的实变量函数理论领域进行研究。根据我的定义，如果一个实数的十进制表示可以由机器编写，那么它就是可计算的。
在第 9 段和第 10 段中，我给出了一些论据来表明可计算数包括所有自然被认为是可计算的数。特别是，我证明了一些大类数字是可计算的。例如，它们包括所有代数数的实部、贝塞尔函数零点的实部、数字 π、e 等。然而，可计算数并不包括所有可定义数，如以下不可计算的可定义数示例所示。
尽管可计算数的类别非常大并且在许多方面与实数的类别相似，但它仍然是可枚举的。在第 8 节中，我考虑了某些看似相反的论点。当其中一个论证得到正确应用时，乍一看，得出的结论与哥德尔*的结论相似。这些结果具有极其重要的应用。特别是，如下所示（§11），解析问题无法有解。
在最近的一篇文章中，Alonzo Church 介绍了“有效可计算性”的想法，这与我的“可计算性”的想法相当，但定义完全不同。关于解决问题，丘奇也得出了类似的结论。本文附录中给出了“可计算性”和“有效可计算”等价性的证明。
1. 电脑
我们已经说过，可计算数是那些小数位可以用有限方法计算的数。这里需要一个更清晰的定义。在我们到达第 9 节之前，本文不会真正尝试证明此处给出的定义的合理性。现在，我只想指出，（逻辑）基本原理是人类的记忆必然是有限的。
让我们将计算实数的人与只能满足有限数量的条件 q1, q2, …, qR 的机器进行比较；我们将这些条件称为“m 配置”。这台（即如此定义的）机器配备有“胶带”（类似于纸）。穿过机器的皮带被分成几段。我们称它们为“正方形”。每个这样的方块都可以包含某种“符号”。在任何时刻，只有一个这样的正方形，比如第 r 个，包含“在这台机器中”的符号。我们将这样的正方形称为“扫描符号”。可以说，“扫描字符”是机器“直接感知”的唯一字符。然而，通过改变它的 m 配置，机器可以有效地记住它之前“看到”（扫描过）的一些字符。机器在任何时刻可能的行为由 m 配置 qn 和扫描的符号***决定。我们称这对符号 qn 为“配置”。这样指定的配置决定了给定机器的可能行为。在其中所扫描的方块是空白的（即，不包含字符）的一些配置中，机器在所扫描的方块上写入新字符，而在这些配置的另一些中，它擦除所扫描的字符。这台机器也能够移动来扫描另一个方格，但这样它只能移动到右侧或左侧的相邻方格。除了这些操作之外，还可以更改机器的 m 配置。在这种情况下，一些写入的字符将形成一个数字序列，这是正在计算的实数的小数部分。其余的无非是为了“帮助记忆”而做的不准确的标记。在这种情况下，只能擦除上述不准确的标记。
我声称这里考虑的操作包括计算中使用的所有操作。对于了解机器理论的读者来说，这种说法的基本原理更容易理解。因此，在下一节中，我将在理解“机器”、“磁带”、“扫描”等术语的基础上继续发展相关理论。
*哥德尔“论数学原理中形式上不可判定的句子（由怀特海和罗素于 1910 年、1912 年和 1913 年出版）和相关系统，第一部分”，《数学杂志》。物理学，德国月刊第 38 期（1931 年，第 173-198 页。
** Alonzo Church，“初等数论中的不可判定问题”，American J. of Math.，第 58 期（1936 年），第 345-363 页。
*** Alonzo Church，“关于解决问题的注释”，J. of Symbolic Logic，第 1 期（1936 年），第 40-41 页
Leave a Reply