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