不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

简介图灵1936年的论文

已有 1462 次阅读 2024-1-5 19:40 |个人分类:图灵论著专研与精译工作群|系统分类:科研笔记

当前蓬勃发展的人工智能揭示出人类面对自身的挑战,当我们从中认识到人类社会出现重大转折时却似乎失去了方向感,比如,人工智能的可解释性一直是一个黑盒子。因此,我们认为,追本溯源重读图灵的著作对理清一直以来困扰人们的数理逻辑和计算机理论的基本难题会有实质性的帮助!

图灵1936论文为计算机技术和科学奠定的基础,这里简介此论文。

图灵1936年的论文正如其题目所示,论可计算数及其在判定问题上的应用(On Computable Numbers, with an Application to the Entscheidungsproblem图灵开篇提出计算数

- 计算数简单被描述成实数,表达成用有限的手段计算的十进制数。虽然本文的主题表面上讲可计算数,然而几乎可以同样容易定义和研究变量为整数或实数或可计算变量的可计算函数,可计算谓词等。在每种情况下,基本的问题是一样的,我选择可计算数来解释,是因为这样可以涉及最少的技术细节。

图灵将人计算实数与机器计算比较,引入计算机器现称图灵机),这样计算机器的计算性就可由计算数来表达。然而由于可计算数是一个不可分割的整体,由此定义的可计算性因此具有整合性,使得图灵得以持系统观建立其可计算性理论,这具有“范式”意义的面向,图灵在论文中并没有特别的强调。

Entscheidungsproblem源自希尔伯特(Hilbert)在1900年巴黎国际数学家大会上提出的23个数学问题中的第10问题 - 判定丢番图方程的可解性。Entscheidungsproblem在一阶谓词系统中的一般表述是问:是否存在判定给定一阶谓词公式可证明的通用过程?

一个计算机器是否具有可计算性,即是否打印出预期的可计算数,是需要判断的,这就是图灵这篇奠基性的论文的主题:证明计算性是不可判定的进而证明Entscheidungsproblem无解。

图灵证明的重点在第8对角线法的应用图灵首先用前面7章的篇幅为第8章作准备:设计计算机器,设计拟任意机器计算的通用计算机器”(“通用图灵机”),定义可计算性(circle-free machine vs circular machine 为枚举可计算数提出机器的编码等;然后,在第8章,图灵应用对角线法证明不存在判定任意机器的可计算性的通用计算机器;最后在论文的第11应用于判定问题图灵运用第8章的结果证明Entscheidungsproblem无解。

图灵的论文共有11章:

1. 计算机器(Computing machines

图灵可将一个人计算实数与一台机器计算比较,引入了计算机器的概念,并为他的计算理论模型(现在称为“图灵机”)的发展奠定了基础。

2. 义(Definitions

图灵定义基本概念,自动机(Automatic machines),计算机器(Computing machines),循环和非循环机器(Circular and circle-free machines),可计算序列和可计算数(Computable sequences and numbers)。

3.计算机器的例子(Examples of computing machines

图灵提供了两种计算机器的例子:第一个计算序列 010101… 的机器;第二个计算稍微困难一些等序列,001011011101111011111

4. 缩写表(Abbreviated tables

图灵引入了缩写表的概念,作为更简洁地表示计算机操作的一种手段。

5. 计算序列的枚举(Enumeration of computable sequences

基于可计算序列是由机器计算的事实,图灵提出了一种对机器进行编码的方法,首先将其表示为标准描述(S.D,然后将标准描述表示为称为机器的描述数(D.N的整数 ,使得枚举机器以及可计算数成为可能。

6. 通用计算机器(The universal computing machine

图灵引入了“通用图灵机”的概念,这一关键思想强调了单个图灵机模拟任何其他图灵机的能力。

7. 通用计算机器详细说明(Detailed description of the universal machine

图灵对通用计算机的构造和操作进行了详细的技术阐述,解释说明机器如何模拟任何其他机器的行为。

8. 对角线过程的应用(Application of the diagonal process

图灵首先应用对角线法证明不存在判定任意机器的可计算性的通用计算机器;然后图灵利用机器D不存在的结果进一步指出,不存在机器E,当给它提供任意机器MS.D时,判定M是否打印一个给定的符号(比如0这才是所谓的停机问题换句话说,停机问题不过是不存在判定任给机器的可计算性的通用过程(机器D的推论。

9. 计算数的范围(The extent of the computable numbers

图灵讨论三种类型的论证有助于理解可计算数的范围:直觉、证明和示例。

10. 计算的大类例子(Examples of large classes of numbers which are computable

图灵指出某些大的类的数是可计算的,它们包括代数数的实数部分,Bessel函数的大小的实数部分,PI, e等等。

11. 应用到 Entscheidungsproblem Application to the Entscheidungsproblem 

图灵将每个计算机M达为一个谓词公式Un(M)证明如果存在一个通用过程来确定Un(M)是否可证明,那么也存在一个通用过程来确定M是否打印0;而第8证明这样的通用过程不存在,所以也就不存在通用过程证明给定的谓词公式是否可证明,于是希尔伯特问题无解。

Reference :

Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936.  https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf



https://m.sciencenet.cn/blog-2322490-1416801.html

上一篇:点评“复杂性理论探索知识极限的 50 年历程”
下一篇:世界逻辑日:“说谎者悖论” - 图灵的视角与哥德尔的视角

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-14 05:28

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部