更改

关于著名数学家大卫•希尔伯特David Hilbert在1900年提出的Hilbert问题，10号问题的一个方面已经浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表达式如下。

关于著名数学家大卫•希尔伯特David Hilbert在1900年提出的Hilbert问题，10号问题的一个方面已经浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表述如下。

{{quote|'''10. Determination of the solvability of a Diophantine equation'''. Given a [[Diophantine equation]] with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

{{quote|'''10. Determination of the solvability of a Diophantine equation'''. Given a [[Diophantine equation]] with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p. 96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "Systems of Logic Based on Ordinals", contains the following definition of "a computable function":

While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" (Hodges p. 96). While at Princeton pursuing his PhD, Turing built a Boolean-logic multiplier (see below). His PhD thesis, titled "Systems of Logic Based on Ordinals", contains the following definition of "a computable function":

虽然Gandy认为Newman的上述言论有“误导性” ，但并非所有人都赞同这一观点。Turing一生都对机器有着浓厚的兴趣: “Alan从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他很可能一开始就问自己，把打字机称为'机械'是什么意思"（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为 "基于序数的逻辑系统"，包含了 "可计算函数 "的如下定义。

虽然Gandy认为Newman的上述言论有“误导性” ，但并非所有人都赞同这一观点。Turing一生都对机器有着浓厚的兴趣: “Alan从小就梦想发明打字机; (他的母亲)图灵夫人有一台打字机; 他很可能一开始就问自己，把打字机称为'机械的'是什么意思"（Hodges p.96）。在普林斯顿攻读博士学位时，图灵制造了一个布尔逻辑乘法器（见下文）。他的博士论文题为 "基于序数的逻辑系统"，包含了 "可计算函数 "的如下定义。

{{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}}

{{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}}

上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么这个函数就是有效的可计算函数"。我们可以从字面上理解这句话，将纯机械过程理解为可以由机器完成的过程。可以用一定的正常形式对这些机器的结构进行数学描述。这些思想的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义第3个是λ可计算性是等价的，虽然有些费力。

上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么这个函数就是有效的可计算函数"。我们可以从字面上理解这句话，将纯机械过程理解为可以由机器完成的过程。可以用一定的正常形式对这些机器的结构进行数学描述。这些思想的发展导致了作者对可计算函数的定义，以及对具有有效可计算性的计算认同。要证明这三个定义第3个是λ可计算性是等价的并不困难，虽然有些费力。

- 图灵(1939)在The Undecidable一书中，第160页。

- 图灵(1939)在The Undecidable一书中，第160页。

{{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}}

{{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}}

希尔伯特-恩赐问题不可能有解......。因此，我提出要证明，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。

希尔伯特-判定问题不可能有解......。因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。

- 摘自Turing的论文，详见The Undecidable，第145页。

- 摘自Turing的论文，详见The Undecidable，第145页。