更改

图灵的例子(他的第二个证明):如果有人要求用一般程序来告诉我们:“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。

图灵的例子(他的第二个证明):如果有人要求用一般程序来告诉我们:“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。

===1937–1970: The "digital computer", the birth of "computer science"==

===1937–1970: "数字计算机"，"计算机科学 "的诞生==

 

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.

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年，在普林斯顿写博士论文的时候，Turing从零开始制造了一个数字(布尔逻辑)乘法器，自制了机电继电器(Hodges p. 138)。“Alan的任务是将图灵机的逻辑设计体现在继电器操作的开关网络中......”(Hodges p. 138)。虽然Turing最初可能只是好奇和试验，但是在德国(Konrad Zuse，1938年)和美国(Howard Aiken，1937年)都在朝着同一个方向努力，他们的劳动成果被轴心国和盟国的军队在二战中使用。Hodges p. 298-299)。在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)将这项工作进一步推进到寄存器和随机存取机器模型ーー但基本上所有这些都只是带有类似算术指令集的多带图灵机。

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年至今：作为计算模型的图灵机===

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:

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:

 

{{quote|Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory:

{{quote|Depending on the objects one likes to manipulate in the computations (numbers like nonnegative integers or alphanumeric strings), two models have obtained a dominant position in machine-based complexity theory:

根据人们在计算中喜欢操作的对象(非负整数或字母数字串等数字)，有两种模型在基于机器的复杂性理论中获得了主导地位：

{{quote|根据人们在计算中喜欢操作的对象(非负整数或字母数字串等)，有两种模型在基于机器的复杂性理论中获得了主导地位：

<blockquote>''the off-line multitape Turing machine''..., which represents the standard model for string-oriented computation, and the ''random access machine (RAM)'' as introduced by Cook and Reckhow ..., which models the idealized Von Neumann style computer.</blockquote>|van Emde Boas 1990:4}}

<blockquote>''the off-line multitape Turing machine''..., which represents the standard model for string-oriented computation, and the ''random access machine (RAM)'' as introduced by Cook and Reckhow ..., which models the idealized Von Neumann style computer.</blockquote>|van Emde Boas 1990:4}}

离线多带图灵机... ，它代表了面向字符串计算的标准模型，以及 Cook 和 Reckhow... 提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。

离线多带图灵机——它代表了面向字符串计算的标准模型，以及Cook和Reckhow提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。

- van Emde Boas 1990:4

- van Emde Boas 1990:4 }}

{{quote|Only in the related area of analysis of algorithms this role is taken over by the RAM model.|van Emde Boas 1990:16}}

{{quote|Only in the related area of analysis of algorithms this role is taken over by the RAM model.|van Emde Boas 1990:16}}

- van Emde Boas 1990:16

- van Emde Boas 1990:16. }}

==See also==

==See also==