113
个编辑
更改
跳到导航
跳到搜索
第732行：
第732行： − When Turing returned to the UK he ultimately became jointly responsible for breaking the German secret codes created by encryption machines called "The Enigma"; he also became involved in the design of the ACE ([[Automatic Computing Engine]]), "[Turing's] ACE proposal was effectively self-contained, and its roots lay not in the [[EDVAC]] [the USA's initiative], but in his own universal machine" (Hodges p. 318). Arguments still continue concerning the origin and nature of what has been named by Kleene (1952) [[Turing's Thesis]]. But what Turing ''did prove'' with his computational-machine model appears in his paper "[[On Computable Numbers, with an Application to the Entscheidungsproblem]]" (1937):+ − 当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器"（Hodges p.318）。关于被Kleene（1952年）命名为 "图灵论文 "的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中"On Computable Numbers, with an Application to the Entscheidungsproblem"。+ − 希尔伯特-判定问题不可能有解......因此我建议，不可能有一个一般的过程来确定函数微积分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". − − 图灵的例子(他的第二个证明):如果有人要求用一般程序来告诉我们:“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。 − − ===1937–1970: "数字计算机"，"计算机科学 "的诞生=== − − In 1937, while at Princeton working on his PhD thesis, Turing built a digital (Boolean-logic) multiplier from scratch, making his own electromechanical relays (Hodges p. 138). "Alan's task was to embody the logical design of a Turing machine in a network of relay-operated switches ..." (Hodges p. 138). While Turing might have been just initially curious and experimenting, quite-earnest work in the same direction was going in Germany ([[Konrad Zuse]] (1938)), and in the United States ([[Howard Aiken]]) and [[George Stibitz]] (1937); the fruits of their labors were used by both the Axis and Allied militaries in [[World War II]] (cf. Hodges p. 298–299). In the early to mid-1950s [[Hao Wang (academic)|Hao Wang]] and [[Marvin Minsky]] reduced the Turing machine to a simpler form (a precursor to the [[Post–Turing machine]] of [[Martin Davis (mathematician)|Martin Davis]]); simultaneously European researchers were reducing the new-fangled [[electronic computer]] to a computer-like theoretical object equivalent to what was now being called a "Turing machine". In the late 1950s and early 1960s, the coincidentally parallel developments of Melzak and Lambek (1961), Minsky (1961), and Shepherdson and Sturgis (1961) carried the European work further and reduced the Turing machine to a more friendly, computer-like abstract model called the [[counter machine]]; Elgot and Robinson (1964), Hartmanis (1971), Cook and Reckhow (1973) carried this work even further with the [[register machine]] and [[random-access machine]] models—but basically all are just multi-tape Turing machines with an arithmetic-like instruction set. − − − 1937年，图灵在普林斯顿大学写博士论文时，从零开始建立了一个数字（布尔逻辑）乘法器，自制了机电继电器（Hodges p.138）。"艾伦的任务是将图灵机的逻辑设计体现在一个由继电器操作的开关网络中......" (Hodges p.138)。德国(Konrad Zuse，1938年)和美国(Howard Aiken，1937年)都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。在20世纪50年代初至中期，Hao Wang 和 Marvin Minsky 将图灵机简化为一种更简单的形式(它是 Martin Davis 的后图灵机的前身) ; 与此同时，欧洲研究人员将这种新型电子计算机简化为一种类似于计算机的理论物体，相当于现在所说的“图灵机”。在20世纪50年代后期和60年代初期， Melzak 和 Lambek (1961)、 Minsky (1961)和 Shepherdson and Sturgis (1961)等人不约而同地展开进一步的研究，推进了欧洲的工作，并将图灵机简化为一个更友好的、类似计算机的抽象模型，称为计数器; Elgot 和 Robinson (1964)、 Hartmanis (1971)、 Cook 和 Reckhow (1973)将这项工作进一步推进到寄存器和随机存取机器模型ーー但基本上所有这些都只是带有类似算术指令集的多带图灵机。 + + − − Today, the counter, register and random-access machines and their sire the Turing machine continue to be the models of choice for theorists investigating questions in the [[theory of computation]]. In particular, [[computational complexity theory]] makes use of the Turing machine: − − + − + − − 只有在算法分析的相关领域，这个角色才能被RAM模型所取代。- van Emde Boas 1990:4 − −
无编辑摘要
上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的"。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。 - 图灵(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"。
希尔伯特-判定问题不可能有解……因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。——摘自图灵的论文，详见《The Undecidable》，第145页。
图灵的例子（他的第二个证明）：如果有人要求用一般程序来告诉我们：“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。
===1937–1970“数字计算机”“计算机科学 ”的诞生===
1937年，图灵在普林斯顿大学写博士论文时，从零开始建立了一个数字（布尔逻辑）乘法器，自制了机电继电器（Hodges p.138）。“艾伦的任务是将图灵机的逻辑设计体现在一个由继电器操作的开关网络中……”（Hodges p.138）。德国（Konrad Zuse，1938年）和美国（Howard Aiken，1937年）都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。在20世纪50年代初至中期，Hao Wang和Marvin Minsky将图灵机简化为一种更简单的形式（它是 Martin Davis的后图灵机的前身）；与此同时，欧洲研究人员将这种新型电子计算机简化为一种类似于计算机的理论物体，相当于现在所说的“图灵机”。在20世纪50年代后期和60年代初期，Melzak和Lambek（1961）、Minsky（1961）和Shepherdson and Sturgis（1961）等人不约而同地展开进一步的研究，推进了欧洲的工作，并将图灵机简化为一个更友好的、类似计算机的抽象模型，称为计数器;；Elgot和Robinson（1964）、 Hartmanis（1971）、Cook 和 Reckhow（1973）将这项工作进一步推进到寄存器和随机存取机器模型——但基本上所有这些都只是带有类似算术指令集的多带图灵机。
===1970年至今：作为计算模型的图灵机===
===1970年至今：作为计算模型的图灵机===
如今，计数器、寄存器和随机存取机以及它们的先驱图灵机仍然是理论家们研究计算理论问题的首选模型。特别是，计算复杂性理论也使用了图灵机。
如今，计数器、寄存器和随机存取机以及它们的先驱图灵机仍然是理论家们研究计算理论问题的首选模型。特别是，计算复杂性理论也使用了图灵机。
根据人们在计算中喜欢操作的对象(非负整数或字母数字串等)，有两种模型在基于机器的复杂性理论中获得了主导地位：
根据人们在计算中喜欢操作的对象(非负整数或字母数字串等)，有两种模型在基于机器的复杂性理论中获得了主导地位：
离线多带图灵机——它代表了面向字符串计算的标准模型，以及Cook和Reckhow提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。——van Emde Boas 1990:4
离线多带图灵机——它代表了面向字符串计算的标准模型，以及Cook和Reckhow提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。- van Emde Boas 1990:4
只有在算法分析的相关领域，这个角色才能被RAM模型所取代。——van Emde Boas 1990:4
==See also==
==See also==
{{divcol|colwidth=22em}}
{{divcol|colwidth=22em}}