150
个编辑
更改
跳到导航
跳到搜索
第739行：
第739行： − {{quote|… the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized…|Gandy p. 55}} 第769行：
第768行： − {{quote|But what Church had done was something rather different, and in a certain sense weaker. ... the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration.|Hodges p. 112}} 第798行：
第796行： − − {{quote|It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.|Turing (1939) in ''The Undecidable'', p. 160}} 第807行：
第803行： − + − {{quote|[that] the Hilbert Entscheidungsproblem can have no solution ... I propose, therefore to show that there can be no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.|from Turing's paper as reprinted in ''The Undecidable'', p. 145}} − −
→历史
Gandy指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p. 53).他引用了其他关于“通用计算机”的理论，包括珀西·卢德盖特（Percy Ludgate， 1909年)、莱昂纳多 · 托雷斯 · 奎维多（Leonardo Torres y Quevedo，1914年)、莫里斯 · d’奥卡涅（Maurice d'Ocagne，1922年)、路易斯 · 库夫尼纳尔（Louis Couffignal，1933年)、万尼瓦尔 · 布什V（annevar Bush，1936年)、霍华德 · 艾肯（Howard Aiken，1937年)。然而:
Gandy指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p. 53).他引用了其他关于“通用计算机”的理论，包括珀西·卢德盖特（Percy Ludgate， 1909年)、莱昂纳多 · 托雷斯 · 奎维多（Leonardo Torres y Quevedo，1914年)、莫里斯 · d’奥卡涅（Maurice d'Ocagne，1922年)、路易斯 · 库夫尼纳尔（Louis Couffignal，1933年)、万尼瓦尔 · 布什V（annevar Bush，1936年)、霍华德 · 艾肯（Howard Aiken，1937年)。然而:
重点是对一个固定的可迭代的算术运算序列进行编程。条件性迭代和条件性转移对于计算机的一般理论的根本重要性没有得到承认...- Gandy，第55页
重点是对一个固定的可迭代的算术运算序列进行编程。条件性迭代和条件性转移对于计算机的一般理论的根本重要性没有得到承认...- Gandy，第55页
问题在于，要回答这个问题，首先需要对“明确的通用规则”下一个精确定义。普林斯顿大学的教授阿朗佐•丘奇（Alonzo Church）将其称为“有效可计算性”，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特（Emil Post）拓展了他的定义，即一个工人按照一张指令表从一个房间移动到另一个房间书写和擦除标记（1936），邱奇和他的两个学生斯蒂芬•克莱恩（Stephen Kleene）和（j.B. Rosser）利用邱奇的λ微积分和哥德尔的递归理论也是如此。丘奇的论文(发表于1936年4月15日)表明，决策问题确实是“无法决策的” ，比图灵早了将近一年(图灵的论文1936年5月28日提交，1937年1月发表)。与此同时，波斯特在1936年秋天提交了一篇短文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明邱奇的λ微积分和他的机器可以计算同样的函数。
问题在于，要回答这个问题，首先需要对“明确的通用规则”下一个精确定义。普林斯顿大学的教授阿朗佐•丘奇（Alonzo Church）将其称为“有效可计算性”，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特（Emil Post）拓展了他的定义，即一个工人按照一张指令表从一个房间移动到另一个房间书写和擦除标记（1936），邱奇和他的两个学生斯蒂芬•克莱恩（Stephen Kleene）和（j.B. Rosser）利用邱奇的λ微积分和哥德尔的递归理论也是如此。丘奇的论文(发表于1936年4月15日)表明，决策问题确实是“无法决策的” ，比图灵早了将近一年(图灵的论文1936年5月28日提交，1937年1月发表)。与此同时，波斯特在1936年秋天提交了一篇短文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明邱奇的λ微积分和他的机器可以计算同样的函数。
但邱奇所做的是完全不同的事情，而且在某种意义上是较差的。......图灵的构造更直接，并提供了最初原则的论据，从而弥补了邱奇证明中的空白。——Hodges，第112页
但邱奇所做的是完全不同的事情，而且在某种意义上是较差的。......图灵的构造更直接，并提供了最初原则的论据，从而弥补了邱奇证明中的空白。——Hodges，第112页
尽管Gandy认为Newman的上述言论有“误导性” ，但这一观点并不为所有人所认同。图灵一生都对机器有着浓厚的兴趣: “阿兰（图灵）从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他很可能一开始就问自己，把打字机称为'机械的'是什么意思"（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为 "基于序数的逻辑系统"，包含了 "可计算函数 "的定义:
尽管Gandy认为Newman的上述言论有“误导性” ，但这一观点并不为所有人所认同。图灵一生都对机器有着浓厚的兴趣: “阿兰（图灵）从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他很可能一开始就问自己，把打字机称为'机械的'是什么意思"（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为 "基于序数的逻辑系统"，包含了 "可计算函数 "的定义:
上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的"。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。 - 图灵(1939)在The Undecidable一书中，第160页。
上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的"。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。 - 图灵(1939)在The Undecidable一书中，第160页。
当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器"（Hodges p.318）。关于被Kleene（1952年）命名为 "图灵论文 "的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中"On Computable Numbers, with an Application to the Entscheidungsproblem"。
当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器"（Hodges p.318）。关于被Kleene（1952年）命名为 "图灵论文 "的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中"On Computable Numbers, with an Application to the Entscheidungsproblem"。
希尔伯特-决策问题不可能有解......因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。- 摘自图灵的论文，详见《The Undecidable》，第145页。
希尔伯特-决策问题不可能有解......。因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。- 摘自图灵的论文，详见The Undecidable，第145页。
Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".
Turing's example (his second proof): If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".