图灵关于可计算数及其在判定问题中的应用翻译.pdf

关于可计算数及其在判定问题中的应用 ——阿兰.图灵 1.计算机器 2.定义 自动运算机器 计算机器 有限循环数与无限循环数 可计算数列和数 3.计算机器实例 4.缩略程序表 更多的实例 5.对于可计算数列的列举问题 6.通用计算机器 7.关于通用机器的细节描述 8.对角论证法的应用 9.可计算数的范围 10. 大量可计算数的实例 11. 判定问题的应用 附录 可计算数可以被简单地描述成一类实数。它们可以表达 成通过有限次运算而得到的小数点后边的数字。尽管这篇论 文的主题明显是关于可计算数的，我们也同样可以以此来定 义并研究一种可计算函数。其中，这种函数的变量可以为整 数、实数、可计算数、可计算语句等。在不同的变量中，最 基本的问题其实是相同的。而我选择了可计算数来进行明确 的论述以实现最优化的技术。我希望不久之后，我就可以给 出关于可计算数与可计算函数彼此之间的关系的解释。这将 包括关于实数变量的函数理论的发展。而这种理论将以可计 算数的形式来表达。根据我的定义，一个数是可计算的当且 仅当它的小数点后边的数可以被计算机写下。 在第九，十节中，我希望通过论证说明可计算数包括所 有自然即可被当做可计算的数。特别的，我说明了大量的数 都是可计算的。它们包括所有代数数中的实数部分和贝塞尔 函数中的零的实数部分，以及数 X、e 等。然而可计算数并 不包括所有可定义数，也将给出一个可定义数并不是可计算 数的例子。 尽管可计算数是如此之多，并且在许多方面与实数相近， 但它仍然是可列举的。在第八章中我们将检测某些看起来能 证明相反的论证。经过正确应用这些论证中的一条，能得到 与戈贝尔极其相似的结论。这些结果都有极有价值的应用。 这尤其论证了希尔伯特可计算问题无解。 在近期一份 AlonzoChurch 的论文中，他引进了有效计算 的概念，与我提出的可计算性基本相同，但定义的方式有很 大不同。Church 就 entscheidungsproblem 也得到了近似的 结论。这两者之间的等价性将在文章后的附录中给出。 1．计算机器 我们已经说过可计算数其小数点后数字可通过有限次计 算得到。这需要更精确的定义。直到第九节才会有验证定义 的可行方法。现在我只能说证明依赖于人类记忆的有限性。 我们可以将人计算一个实数的过程和一台只能识别叫做 m-构造的有限个状态，如 q1.q2„„qR，的机器相对比。向 机器提供一被分成各自能承载一记号的许多小节称为方格 的磁带与纸条类似，并使其穿过机器。任何时刻机器中都只 有一个装载着记号 S(r)的方阵 r-th。我们称这个方阵为被 扫描的方阵。其上装载的记号叫做被扫描的记号。这个记号 可以理解为机器唯一能直接识别的记号。然而，通过修改它 的 m-构造，机器可以有效的记住它之前扫描过的记号。机器 在任何时刻可能的动作都决定于它的 m-配置 qn 和被其扫描 的记号S(r)。这组qn 和 S(r)叫做机器的构造，因此构造决 定了机器所有可能的行为。在一些构造中被扫描的方阵是空 白的（不装载任何记号），这是机器会在其上写下一个新的 记号；在其他构造中机器会擦除一些扫描的记号。机器也会 改变正在被扫描的方阵，但只是将它交换到左面或右面的位 置。除了这些操作外，其他任何操作都会使机器 m-构造改变。 一些写下的记号将形成一列数据，记录正在被计算的实数的 小数点后数字。其他只是促进记忆的草拟的记录。只有这些 草拟记录是易于擦除的。 我的观点是这些操作包含了所有计算过程中会用到的操 作。这个论点的证明在读者熟悉了计算机理论后将更加容易 理解。因此在下一节中我将从理论的发展着手并假设读者理 解机器、磁带、被扫描等词的含义。 2．定义 自动机：如果在每一阶段机器的动作都完全由其构造决 定，则称其为自动机（或 a-机器）。在某些情况下我们也会 使用动作只部分由构造决定的机器（选择机或 c-机器）（因 此在第一节中使用可能一词）。当这类机器遇到一个模糊的 构造便需要有外界操作加以选择。当我们运用机器处理通则 系统时便会遇到这种情况。这篇文章中只研究自动机的情况， 因此将经常省略前缀a-。