五二小说网

手机浏览器扫描二维码访问

第五课 普林斯顿大学名人榜人工智能之父阿兰图灵（第4页）

图灵机的概念有十分独特的意义：如果把图灵机的内部状态解释为指令，用字母表的字来表示，与输出字输入字同样存贮在机器里，那就成为电子计算机了。

由此开创了“自动机”

这一学科分支，促进了电子计算机的研制工作。

在给出通用图灵机的同时，图灵就指出，通用图灵机在计算时，其“机械性的复杂性”

是有临界限度的，超过这一限度，就要靠增加程序的长度和存贮量来解决。

这种思想开启了后来计算机科学中计算复杂性理论的先河。

判定问题

所谓“判定问题”

指判定所谓“大量问题”

是否具有算法解，或者是否存在能行性的方法使得对该问题类的每一个特例都能在有限步骤内机械地判定它是否具有某种性质的问题。

艾伦·麦席森·图灵在判定问题上的一大成就是把图灵机的“停机问题”

作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题：“如果问题A可判定，则停机问题可判定。”

从而由“停机问题是不可判定的”

推出“问题A是不可判定的”

。

所谓停机指图灵机内部达到一个结果状态、指令表上没有的状态或符号对偶，从而导致计算终止。

在每一时刻，机器所处的状态，纸带上已被写上符号的所有格子以及机器当前注视的格子位置，统称为机器的格局。

图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列。

此过程可能无限制继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。

在结束状态下停机所达到的格局是最终格局，此最终格局就包含机器的计算结果。

所谓停机问题即是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机?图灵证明，这样的算法是不存在的，即停机问题是不可判定的，从而使之成为解决许多不可判定性问题的基础。

1937年，阿兰·麦席森·图灵用他的方法解决了著名的希尔伯特判定问题：狭谓词演算公式的可满足性的判定问题。

他用一阶逻辑中的公式对图灵机进行编码，再由图灵机停机问题的不可判定性推出一阶逻辑的不可判定性。

他在此处创用的“编码法”

成为后来人们证明一阶逻辑的公式类的不可判定性的主要方法之一。

在判定问题上，艾伦·麦席森·图灵的另一成就是1939年提出的带有外部信息源的图灵机概念，并由此导出“图灵可归约”

及相对递归的概念。

运用归约和相对递归的概念，可对不可判定性与非递归性的程度加以比较。

在此基础上，E.波斯特（Post）提出了不可解度这一重要概念，这方面的工作后来有重大的进展。

图灵参与解决的另一个著名的判定问题是“半群的字的问题”

，它是图埃（Thue）在1914年提出来的：对任意给定的字母表和字典，是否存在一种算法能判定两个任意给定的字是否等价，给出有限个不同的称为字母的符号，便给出了字母表，字母的有限序列称为该字母表上的字。

如果两个字R和S使用有限次字典之后可以彼此变换，则称这两个字是等价的。

1947年，波斯特和马尔科夫（Markov）用图灵的编码法证明了这一问

【学校荣誉】

在普林斯顿大学260年的建校史上，出过不少星光灿烂的人物，对美国的社会文明做出过很大的贡献，从这所学校里走出过大批的科学家、文学家和政治家。

著名的相对论大师爱因斯坦、数学大师冯·诺伊曼·阿廷等都在这里从事过研究。