图灵机 - 版本历史

薄荷：/* 与实际机器的比较 */

2021-08-22T15:00:16Z

与实际机器的比较

薄荷：/* 图灵机概述 */

2021-08-22T14:59:34Z

图灵机概述

2021年8月21日 (六) 06:45 SyouTK

2021-08-21T06:45:38Z

显示更改

2021年8月20日 (五) 07:43 SyouTK

2021-08-20T07:43:32Z

2021年8月20日 (五) 07:17 SyouTK

2021-08-20T07:17:16Z

显示更改

2021年8月20日 (五) 06:46 SyouTK

2021-08-20T06:46:07Z

2021年8月20日 (五) 06:37 SyouTK

2021-08-20T06:37:52Z

显示更改

2021年8月18日 (三) 04:15 SyouTK

2021-08-18T04:15:46Z

2021年8月15日 (日) 09:14 SyouTK

2021-08-15T09:14:01Z

2021年8月15日 (日) 05:41 SyouTK

2021-08-15T05:41:55Z

@@ 第461行： / 第461行： @@
 # 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
 # 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
-# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机 deterministic finite automaton,DFA却有四千亿个状态。这使得DFA的表示方式无法分析。
+# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机 deterministic finite automaton（DFA）却有四千亿个状态。这使得DFA的表示方式无法分析。
 # 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。
 # 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用，因为它们有任意精度的数据类型可用，而且永远不必处理意外情况（包括但不限于内存耗尽）。

@@ 第26行： / 第26行： @@
 图灵机能够处理不受限制的语法，这意味着它能够以无限多的方式鲁棒地评价一阶逻辑。通过λ运算可以证明这一点。
-能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇 Alonzo Church，美国著名数学家'''提出了一个更具有普适性的数学定义。他将在λ运算的工作和图灵在正式计算机理论中的工作融合，称为邱奇-图灵理论。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
+能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇 Alonzo Church'''，美国著名数学家，提出了一个更具有普适性的数学定义。他将在λ运算的工作和图灵在正式计算机理论中的工作融合，称为邱奇-图灵理论。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
 ===物理描述===

←上一版本		2021年8月20日 (五) 07:43的版本
第13行：		第13行：

	因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。		因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。
−
−	~~[[[文件:图灵机.jpg\|缩略图\| right\| 图灵机的理想模型]]]~~

	图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器（Random-access memory）。		图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器（Random-access memory）。

@@ 第1行： / 第1行： @@
 '''图灵机'''是一种数学计算模型，定义了一个抽象的机器，该机器可以根据指定的规则表在纸带上进行操作。虽然图灵机模型非常简单，但是图灵机可以模拟任何给定的计算机算法。
@@ 第651行： / 第655行： @@
 * Rogozhin, Yurii, 1998, "[https://web.archive.org/web/20050308141040/http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm A Universal Turing Machine with 22 States and 2 Symbols]", ''Romanian Journal of Information Science and Technology'', 1(3), 259–265, 1998. (surveys known results about small universal Turing machines)
-* [[Stephen Wolfram]], 2002, [http://www.wolframscience.com/nksonline/page-707 ''A New Kind of Science''], Wolfram Media, {{isbn|1-57955-008-8}}
+* Stephen Wolfram, 2002, [http://www.wolframscience.com/nksonline/page-707 ''A New Kind of Science''], Wolfram Media, {{isbn|1-57955-008-8}}
 * Brunfiel, Geoff, [http://www.nature.com/news/2007/071024/full/news.2007.190.html Student snags maths prize], ''Nature'', October 24. 2007.
@@ 第674行： / 第678行： @@
 * {{cite book|author = Martin Davis | year = 2000| title = Engines of Logic: Mathematicians and the origin of the Computer| publisher = W. W. Norton & Company, New York| edition = 1st | isbn = 978-0-393-32229-3| author-link = Martin Davis (mathematician)}}
-* [[Robin Gandy]], "The Confluence of Ideas in 1936", pp.&nbsp;51–102 in [[Rolf Herken]], see below.
+* Robin Gandy, "The Confluence of Ideas in 1936", pp.&nbsp;51–102 in [[Rolf Herken]], see below.
-* [[Stephen Hawking]] (editor), 2005, ''God Created the Integers: The Mathematical Breakthroughs that Changed History'', Running Press, Philadelphia, {{isbn|978-0-7624-1922-7}}. Includes Turing's 1936–1937 paper, with brief commentary and biography of Turing as written by Hawking.
+* Stephen Hawking (editor), 2005, ''God Created the Integers: The Mathematical Breakthroughs that Changed History'', Running Press, Philadelphia, {{isbn|978-0-7624-1922-7}}. Includes Turing's 1936–1937 paper, with brief commentary and biography of Turing as written by Hawking.
 * {{cite book | author = Rolf Herken | title = The Universal Turing Machine—A Half-Century Survey | publisher = Springer Verlag | isbn = 978-3-211-82637-9 | year = 1995}}
-* [[Andrew Hodges]], ''[[Alan Turing: The Enigma]]'', [[Simon and Schuster]], New York. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
+* Andrew Hodges, ''Alan Turing: The Enigma'', Simon and Schuster, New York. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
 * {{cite book|author = Ivars Peterson | year = 1988| title = The Mathematical Tourist: Snapshots of Modern Mathematics|url = https://archive.org/details/mathematicaltour00pete |url-access = registration | publisher = W. H. Freeman and Company, New York| edition = 1st | isbn = 978-0-7167-2064-5 | author-link = Ivars Peterson}}
-* [[Roger Penrose]], ''The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics'', [[Oxford University Press]], Oxford and New York, 1989 (1990 corrections), {{isbn|0-19-851973-7}}.
+* Roger Penrose, ''The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics'', Oxford University Press, Oxford and New York, 1989 (1990 corrections), {{isbn|0-19-851973-7}}.
 * {{cite book | author = Paul Strathern | title = Turing and the Computer—The Big Idea | publisher = Anchor Books/Doubleday | isbn = 978-0-385-49243-0 | year = 1997 | url = https://archive.org/details/turingcomputer00stra | author-link = Paul Strathern }}
-* [[Hao Wang (academic)|Hao Wang]], "A variant to Turing's theory of computing machines", ''Journal of the Association for Computing Machinery'' (JACM) 4, 63–92 (1957).
+* Hao Wang (academic)|Hao Wang, "A variant to Turing's theory of computing machines", ''Journal of the Association for Computing Machinery'' (JACM) 4, 63–92 (1957).
-* [[Charles Petzold]], [http://www.theannotatedturing.com/ Petzold, Charles, ''The Annotated Turing''], John Wiley & Sons, Inc., {{isbn|0-470-22905-5}}
+* Charles Petzold, [http://www.theannotatedturing.com/ Petzold, Charles, ''The Annotated Turing''], John Wiley & Sons, Inc., {{isbn|0-470-22905-5}}
 * Arora, Sanjeev; Barak, Boaz, [http://www.cs.princeton.edu/theory/complexity/ "Complexity Theory: A Modern Approach"], Cambridge University Press, 2009, {{isbn|978-0-521-42426-4}}, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
@@ 第703行： / 第707行： @@
 * [http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks] by Enrique Zeleny as part of the Wolfram Demonstrations Project.
-类别: 1936年
+----
-类别: 1937年
+'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
-类别: 可计算性理论
+[[category:理论计算机科学]]
-类别: 英国发明
+[[category:计算模型]]
-类别: 自动机(计算)
+[[category:可计算性理论]]

@@ 第4行： / 第4行： @@
 图灵机是1936年由'''阿兰·图灵（Alan Turing）'''发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:
-# 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
+:: 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
-# 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
+:: 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
 因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。

@@ 第732行： / 第732行： @@
       上面说过，"如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的"。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。 - 图灵(1939)在The Undecidable一书中，第160页。
-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.&nbsp;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"。
-当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了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页。
+图灵的例子（他的第二个证明）：如果有人要求用一般程序来告诉我们：“这台机器是否曾经打印过0”，这个问题就是“无法确定的”。
 ===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==
 {{divcol|colwidth=22em}}

@@ 第50行： / 第50行： @@
 在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
 机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
 在Hopcroft和Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：
 * Г是有限的、非空的纸带''字母符号集''；
 * bᕮГ，是''空白符号''（唯一允许在计算过程中的任何步骤无限频繁地出现在纸带上的符号）；
@@ 第65行： / 第61行： @@
 * F⊆Q是''最终状态''或''接受状态''的集合。初始纸带内容被认为是''接受''由M如果它最终停止在一个状态 F.
 * δ: （Q \ F) Χ Г Χ {L, R}是一个偏函数，称为''转移函数''，其中 L 是左移，R 是右移。如果在当前状态和当前纸带符号上未定义，则机器停止；直观地，转移函数指定了从当前状态转移的下一个状态，哪个符号覆盖读写头指向的当前符号，以及下一个读写头运动。
 此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。
@@ 第77行： / 第71行： @@
 三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）
 * Q={A, B, C, HALT}(状态);
 * Г= {0, 1}(纸带符号);
@@ 第132行： / 第125行： @@
 ==可视化或实现图灵机所需的其他细节==
 用Van Emde Boas (1990)的话来说: “集合论对象(类似于上面的七元组描述形式)只提供了关于机器将如何运行以及它的计算将是什么样子的部分信息。”
 例如，
 * 符号到底是什么样子的，需要有很多决策，也需要有一种万无一失的方法来无穷尽地读写符号。
 * 左移和右移操作可能会使读写头在纸带上移动，但在实际构建图灵机时，更实际的做法是让纸带在读写头下来回滑动。
 * 纸带可以是有限的，并根据需要自动延伸出空白（这是最接近数学定义的），但更常见的是将其视为在一端或两端无限延伸，除了读写头所在的明确给定的有限片段外，都会被预先填充空白。(当然，这在实践中是无法实现的。)纸带的长度不能是固定的，因为那不符合给定的定义，而且会严重限制机器可以执行的计算范围，如果纸带与输入大小成正比，则为线性有界自动机的计算范围，如果纸带是严格的固定长度，则为有限状态机的计算范围。
 ===其他定义===
 文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N("无 "或 "无操作")将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。