Editing Turing machine (section)

==References==
{{citation style|date=November 2019}}<!--mix of footnotes plus inline Harvard references-->
{{Reflist}}

===Primary literature, reprints, and compilations===
* B. [[Jack Copeland]] ed. (2004), ''The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma,'' Clarendon Press (Oxford University Press), Oxford UK, {{isbn|0-19-825079-7}}. Contains the Turing papers plus a draft letter to [[Emil Post]] re his criticism of "Turing's convention", and Donald W. Davies' ''Corrections to Turing's Universal Computing Machine''
* [[Martin Davis (mathematician)|Martin Davis]] (ed.) (1965), ''The Undecidable'', Raven Press, Hewlett, NY.
* Emil Post (1936), "Finite Combinatory Processes—Formulation 1", ''Journal of Symbolic Logic'', 1, 103–105, 1936. Reprinted in ''The Undecidable'', pp.&nbsp;289ff.
* Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", ''Journal of Symbolic Logic'', vol. 12, pp.&nbsp;1–11. Reprinted in ''The Undecidable'', pp.&nbsp;293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on [[Turing's proof|Turing's first and second proofs]].
* {{Cite journal | last= Turing | first= A.M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | url=https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf|journal = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–265 | doi= 10.1112/plms/s2-42.1.230 | s2cid= 73712 }}
* {{Cite journal | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 | issue = 6 }} Reprinted in ''The Undecidable'', pp.&nbsp;115–154.
* Alan Turing, 1948, "Intelligent Machinery."  Reprinted in "Cybernetics: Key Papers." Ed. C.R. Evans and A.D.J. Robertson.  Baltimore: University Park Press, 1968. p.&nbsp;31.  Reprinted in {{Cite journal | doi = 10.1093/philmat/4.3.256| title = Intelligent Machinery, A Heretical Theory| journal = Philosophia Mathematica| volume = 4| issue = 3| pages = 256–260| year = 1996| last1 = Turing | first1 = A. M.| doi-access = free}}
* F. C. Hennie and [[R. E. Stearns]]. ''Two-tape simulation of multitape Turing machines''. [[JACM]], 13(4):533–546, 1966.

===Computability theory===
* {{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 | orig-year = 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.
* [[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 | author-link = Martin Davis (mathematician)}}. 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 =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|last1 = Hopcroft | first1 = John | author-link1 = John Hopcroft | last2 = Ullman | first2 = Jeffrey | author-link2 = 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}}
* [[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. | author-link = 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.&nbsp;225ff and 2.6 ''History and Bibliography''pp.&nbsp;456ff.
* [[Zohar Manna]], 1974, ''[[Mathematical Theory of Computation]]''. Reprinted, Dover, 2003. {{isbn|978-0-486-43238-0}}
* [[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
* {{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.&nbsp;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.)
* {{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.&nbsp;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 }}
* [[Peter van Emde Boas]] 1990, ''Machine Models and Simulations'', pp.&nbsp;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.

===Church's thesis===
* {{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 |access-date=2008-10-15}}
* {{cite book|author = Roger Penrose | orig-year = 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}}

===Small 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}}
* Brunfiel, Geoff, [http://www.nature.com/news/2007/071024/full/news.2007.190.html Student snags maths prize], ''Nature'', October 24. 2007.
* Jim Giles (2007), [https://www.newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html Simplest 'universal computer' wins student $25,000], New Scientist, October 24, 2007.
* Alex Smith, [http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf Universality of Wolfram's 2, 3 Turing Machine], Submission for the Wolfram 2, 3 Turing Machine Research Prize.
* Vaughan Pratt, 2007, "[http://cs.nyu.edu/pipermail/fom/2007-October/012156.html Simple Turing machines, Universality, Encodings, etc.]", FOM email list. October 29, 2007.
* Martin Davis, 2007, "[http://cs.nyu.edu/pipermail/fom/2007-October/012132.html Smallest universal machine]", and [http://cs.nyu.edu/pipermail/fom/2007-October/012145.html Definition of universal Turing machine] FOM email list. October 26–27, 2007.
* Alasdair Urquhart, 2007 "[http://cs.nyu.edu/pipermail/fom/2007-October/012140.html Smallest universal machine]", FOM email list. October 26, 2007.
* Hector Zenil (Wolfram Research), 2007 "[http://cs.nyu.edu/pipermail/fom/2007-October/012163.html smallest universal machine]", FOM email list. October 29, 2007.
* Todd Rowland, 2007, "[http://forum.wolframscience.com/showthread.php?s=&threadid=1472 Confusion on FOM]", Wolfram Science message board, October 30, 2007.
* Olivier and Marc RAYNAUD, 2014, [http://www.machinedeturing.com/ang_default.asp A programmable prototype to achieve Turing machines] {{Webarchive|url=https://web.archive.org/web/20160114140003/http://machinedeturing.com/ang_default.asp |date=2016-01-14 }}" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).

===Other===
* {{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.
* [[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.
* {{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}}.
* {{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).
* [[Charles Petzold]], [http://www.theannotatedturing.com/ ''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"
* {{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 }}
* 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.