113
个编辑
更改
无编辑摘要
* {{cite book | last = Boolos | first = George |author2=Richard Jeffrey | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool_r8y9 | url-access = registration | edition = 3rd | publisher = Cambridge University Press | location = Cambridge UK | origyear = 1989| year = 1999| isbn = 0-521-20402-X }}
* {{cite book | last = Boolos | first = George |author2=Richard Jeffrey | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool_r8y9 | url-access = registration | edition = 3rd | publisher = Cambridge University Press | location = Cambridge UK | origyear = 1989| year = 1999| isbn = 0-521-20402-X }}
* {{cite book | last = Boolos | first = George |author2=John Burgess |author3=Richard Jeffrey | title = Computability and Logic | edition = 4th | publisher = Cambridge University Press | location = Cambridge UK | year = 2002 | isbn = 0-521-00758-5 }} Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf. [[Register machine]]) and [[Computable function|recursive functions]], showing their equivalence.
* {{cite book | last = Boolos | first = George |author2=John Burgess |author3=Richard Jeffrey | title = Computability and Logic | edition = 4th | publisher = Cambridge University Press | location = Cambridge UK | year = 2002 | isbn = 0-521-00758-5 }} Some parts have been significantly rewritten by Burgess. Presentation of Turing machines in context of Lambek "abacus machines" (cf. Register machine) and Computable function|recursive functions, showing their equivalence.
* Taylor L. Booth (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX ''Turing Machines'' includes some recursion theory.
* Taylor L. Booth (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York. Graduate level engineering text; ranges over a wide variety of topics, Chapter IX ''Turing Machines'' includes some recursion theory.
* {{cite book|author = Martin Davis | year = 1958| title = Computability and Unsolvability| publisher = McGraw-Hill Book Company, Inc, New York}} On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
* {{cite book|author = Martin Davis | year = 1958| title = Computability and Unsolvability| publisher = McGraw-Hill Book Company, Inc, New York}} On pages 12–20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x ≥ y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.
* {{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker|author3-link=Elaine Weyuker | title = Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994 | isbn = 0-12-206382-1}}
* {{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker |title = Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994 | isbn = 0-12-206382-1}}
* {{cite book|last =Hennie |first = Fredrick | year = 1977| title = Introduction to Computability| publisher = Addison–Wesley, Reading, Mass|id=QA248.5H4 1977 }}. On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'.
* {{cite book|last =Hennie |first = Fredrick | year = 1977| title = Introduction to Computability| publisher = Addison–Wesley, Reading, Mass|id=QA248.5H4 1977 }}. On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'.
* {{cite book|author = [[John Hopcroft]] and [[Jeffrey Ullman]] | year = 1979| title = Introduction to Automata Theory, Languages, and Computation| title-link = Introduction to Automata Theory, Languages, and Computation| publisher = Addison–Wesley, Reading Mass| edition = 1st | isbn = 0-201-02988-X}} Centered around the issues of machine-interpretation of "languages", NP-completeness, etc.
* {{cite book|author = John Hopcroft and Jeffrey Ullman | year = 1979| title = Introduction to Automata Theory, Languages, and Computation| title-link = Introduction to Automata Theory, Languages, and Computation| publisher = Addison–Wesley, Reading Mass| edition = 1st | isbn = 0-201-02988-X}} Centered around the issues of machine-interpretation of "languages", NP-completeness, etc.
* {{cite book | last = Hopcroft | first = John E.|author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title = Introduction to Automata Theory, Languages, and Computation| edition = 2nd | publisher = Addison–Wesley | location = Reading Mass | year = 2001 | isbn = 0-201-44124-1}} Distinctly different and less intimidating than the first edition.
* {{cite book | last = Hopcroft | first = John E.|author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title = Introduction to Automata Theory, Languages, and Computation| edition = 2nd | publisher = Addison–Wesley | location = Reading Mass | year = 2001 | isbn = 0-201-44124-1}} Distinctly different and less intimidating than the first edition.
* [[Stephen Kleene]] (1952), ''Introduction to Metamathematics'', North–Holland Publishing Company, Amsterdam Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII ''Computable functions'' is on Turing machine proofs of computability of recursive functions, etc.
* Stephen Kleene (1952), ''Introduction to Metamathematics'', North–Holland Publishing Company, Amsterdam Netherlands, 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII ''Computable functions'' is on Turing machine proofs of computability of recursive functions, etc.
* {{cite book | last = Knuth | first = Donald E. | authorlink = Donald Knuth | title = Volume 1/Fundamental Algorithms: The Art of computer Programming| edition = 2nd | publisher = Addison–Wesley Publishing Company| location = Reading, Mass.| year = 1973 }}. With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 ''History and Bibliography'' pp. 225ff and 2.6 ''History and Bibliography''pp. 456ff.
* {{cite book | last = Knuth | first = Donald E. |title = Volume 1/Fundamental Algorithms: The Art of computer Programming| edition = 2nd | publisher = Addison–Wesley Publishing Company| location = Reading, Mass.| year = 1973 }}. With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 ''History and Bibliography'' pp. 225ff and 2.6 ''History and Bibliography''pp. 456ff.
* [[Zohar Manna]], 1974, ''[[Mathematical Theory of Computation]]''. Reprinted, Dover, 2003. {{isbn|978-0-486-43238-0}}
* Zohar Manna, 1974, ''Mathematical Theory of Computation''. Reprinted, Dover, 2003.
* [[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.
* Marvin Minsky, ''Computation: Finite and Infinite Machines'', Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem." Excellent, i.e. relatively readable, sometimes funny.
* {{cite book|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1| author-link = Christos Papadimitriou }} Chapter 2: Turing machines, pp. 19–56.
* {{cite book|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 2: Turing machines, pp. 19–56.
* [[Hartley Rogers, Jr.]], ''Theory of Recursive Functions and Effective Computability'', The MIT Press, Cambridge MA, paperback edition 1987, original McGraw-Hill edition 1967, {{isbn|0-262-68052-1}} (pbk.)
* Hartley Rogers, Jr.''Theory of Recursive Functions and Effective Computability'', The MIT Press, Cambridge MA, paperback edition 1987, original McGraw-Hill edition 1967 (pbk.)
* {{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url = https://archive.org/details/introductiontoth00sips | author-link = Michael Sipser }} Chapter 3: The Church–Turing Thesis, pp. 125–149.
* {{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url = https://archive.org/details/introductiontoth00sips}} Chapter 3: The Church–Turing Thesis, pp. 125–149.
* {{cite book | last = Stone | first = Harold S. | title = Introduction to Computer Organization and Data Structures| edition = 1st | publisher = McGraw–Hill Book Company | location = New York | year = 1972 | isbn = 0-07-061726-0 }}
* {{cite book | last = Stone | first = Harold S. | title = Introduction to Computer Organization and Data Structures| edition = 1st | publisher = McGraw–Hill Book Company | location = New York | year = 1972 | isbn = 0-07-061726-0 }}
* [[Peter van Emde Boas]] 1990, ''Machine Models and Simulations'', pp. 3–66, in [[Jan van Leeuwen]], ed., ''Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity'', The MIT Press/Elsevier, [place?], {{isbn|0-444-88071-2}} (Volume A). QA76.H279 1990. Valuable survey, with 141 references.
* Peter van Emde Boas 1990, ''Machine Models and Simulations'', pp. 3–66, in Jan van Leeuwen, ed., ''Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity'', The MIT Press/Elsevier (Volume A). QA76.H279 1990. Valuable survey, with 141 references.
===丘奇的论文===
===丘奇的论文===
* {{cite journal |author=Nachum Dershowitz |author2=Yuri Gurevich |date=September 2008 |title=A natural axiomatization of computability and proof of Church's Thesis |journal=Bulletin of Symbolic Logic |volume=14 |issue=3 |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf |accessdate=2008-10-15}}
* {{cite journal |author=Nachum Dershowitz |author2=Yuri Gurevich |date=September 2008 |title=A natural axiomatization of computability and proof of Church's Thesis |journal=Bulletin of Symbolic Logic |volume=14 |issue=3 |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf |accessdate=2008-10-15}}
* {{cite book|author = Roger Penrose | origyear = 1989| year = 1990 | title = The Emperor's New Mind | publisher = Oxford University Press, New York| edition = 2nd | isbn = 0-19-851973-7| author-link = Roger Penrose}}
* {{cite book|author = Roger Penrose | origyear = 1989| year = 1990 | title = The Emperor's New Mind | publisher = Oxford University Press, New York| edition = 2nd}}
===小型图灵机===
===小型图灵机===
* 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)
* 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.
* Brunfiel, Geoff, [http://www.nature.com/news/2007/071024/full/news.2007.190.html Student snags maths prize], ''Nature'', October 24. 2007.
* Brunfiel, Geoff, [http://www.nature.com/news/2007/071024/full/news.2007.190.html Student snags maths prize], ''Nature'', October 24. 2007.
===其他===
===其他===
* {{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)}}
* {{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}}
* Robin Gandy, "The Confluence of Ideas in 1936", pp. 51–102 in [[Rolf Herken]], see below.
* Robin Gandy, "The Confluence of Ideas in 1936", pp. 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. 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}}
* {{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}}
* {{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}}
* 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).
* {{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 }}
* {{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}}
* 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.
* 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"
* Arora, Sanjeev; Barak, Boaz, [http://www.cs.princeton.edu/theory/complexity/ "Complexity Theory: A Modern Approach"], Cambridge University Press, 2009, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
* {{cite journal |title=A note on turing machine computability of rule driven systems |date=December 1, 2005 |doi=10.1145/1107523.1107525 |issue=4 |volume=36 |pages=109–110 |journal=[[SIGACT News]] |first=Isaiah Pinchas |last=Kantorovitz|s2cid=31117713 }}
* {{cite journal |title=A note on turing machine computability of rule driven systems |date=December 1, 2005 |doi=10.1145/1107523.1107525 |issue=4 |volume=36 |pages=109–110 |journal=SIGACT News |first=Isaiah Pinchas |last=Kantorovitz}}
* Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: [http://researchprofiles.herts.ac.uk/portal/en/publications/on-undecidability-results-of-real-programming-languages(d3f3aac0-d9da-4756-a421-b4f9ae0cf95f).html "On Undecidability Results of Real Programming Languages"], In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.
* Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: [http://researchprofiles.herts.ac.uk/portal/en/publications/on-undecidability-results-of-real-programming-languages(d3f3aac0-d9da-4756-a421-b4f9ae0cf95f).html "On Undecidability Results of Real Programming Languages"], In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.
* [http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks] by Enrique Zeleny as part of the Wolfram Demonstrations Project.
* [http://demonstrations.wolfram.com/TuringMachineCausalNetworks/ Turing Machine Causal Networks] by Enrique Zeleny as part of the Wolfram Demonstrations Project.
==编者推荐==
===集智文章推荐===
*[https://swarma.org/?p=3652 神经网络与图灵机的复杂度博弈]
::1931年，天才数学家图灵提出了著名的图灵机模型，它奠定了人工智能的数学基础。1943年，麦克洛克 & 皮茨（McCulloch & Pitts）两人提出了著名的人工神经元模型，该模型一直沿用至今，它奠定了所有深度学习模型的基础。那么，这两个开山之作究竟是怎样一种相爱相杀的关系呢？天才数学家冯诺依曼指出，图灵机和神经元本质上虽然彼此等价，我们可以用图灵机模拟神经元，也可以用神经元模拟图灵机，但是它们却位于复杂度王国中的不同领地。神经网络代表了一大类擅长并行计算的复杂系统，它们自身的结构就构成了对自己最简洁的编码；而图灵机则代表了另一类以穿行方式计算的复杂系统，这些系统以通用图灵机作为复杂度的分水岭：一边，系统的行为可以被更短的代码描述；另一边，我们却无法绕过复杂度的沟壑。而先进的深度学习研究正在试图将这两类系统合成为一个：神经图灵机。
===课程推荐===
*[https://campus.swarma.org/course/1155 图灵机]
::本课程将围绕图灵机，详细介绍图灵机的定义、图灵机的计算、图灵机框架的模拟、通用图灵机、以及图灵停机问题，说明算法的上界。
*[https://campus.swarma.org/course/1153 人工智能2020]
::本课程为北京师范大学系统科学学院张江教授开设的研究生课程《人工智能》课程回放。课程偏重理论，辅以编程实践，将粗粒度的梳理人工智能重要的理念、算法、模型。前面会包含一些人工智能之前的理论计算机模型，图灵机等，后面系统从两方面讲解，一是符号派的人工智能，包括搜索、推理、表示等；二是连接派的人工智能，机器学习，强调理论机器学习基础。
===文章推荐===
*[https://pattern.swarma.org/paper?id=9207a15c-9b1d-11ea-abd6-0242ac1a0005 分子计算：通向化学图灵机的途径。]
::为了顺应快速增长的信息存储和处理需求，需要新的计算策略。分子计算的想法（即通过分子、超分子或生物分子方法进行基本计算，而不是通过电子方法）长期以来一直吸引着研究人员。使用分子和(生物)大分子进行计算的前景并非没有先例。自然中充满了以高效率、低能量成本和高密度信息编码来处理和存储数据的示例。根据通用计算方法运行的计算机的设计和组装，例如图灵机中的计算机，未来可能会以化学的方式实现。从这个角度来看，本文章重点介绍了到目前为止已经设计和合成的分子和(生物)大分子系统，目的是将它们用于计算目的；还提出了分子图灵机的蓝图，它基于一个催化装置，它沿着聚合物带滑动，在移动时，以氧原子的形式在这条带上打印二进制信息。
[[文件:展示现代计算技术和未来分子计算的发现和进展的时间表.jpg|缩略图|右]]
*[https://pattern.swarma.org/paper?id=14ecc15e-8860-11ea-b132-0242ac1a000b 使用图灵机的图灵模式：出现和低层次结构形成。]
::尽管阿兰·图灵(Alan Turing)在1952年发表的关于形态发生的论文中提出了常微分方程的反应扩散模型，反映了他对数学生物学的兴趣，但他从未被认为接近过细胞自动机的定义。然而，他对形态发生的处理，特别是他发现的与对称破缺导致的某些形式的不均匀分布有关的困难，是将他的普遍计算理论与他的生物模式形成理论联系起来的关键。建立这样的联系并不能克服图灵所担心的特殊困难，无论如何，这个问题已经在生物学上得到了解决。但相反，这里开发的方法抓住了图灵最初关心的问题，并通过算法概率的概念为更一般的问题提供了一个低级解决方案，从而将图灵模式形成和通用计算这两个他对科学最重要的贡献联系在了一起。本文将展示使用此方法的一维模式的实验结果，而不会损失对n维模式泛化的一般性。
----
----