References Turing machine

1 references

1.1 primary literature, reprints, , compilations
1.2 computability theory
1.3 church s thesis
1.4 small turing machines
1.5 other

references

primary literature, reprints, , compilations

b. jack copeland ed. (2004), essential turing: seminal writings in computing, logic, philosophy, artificial intelligence, , artificial life plus secrets of enigma, clarendon press (oxford university press), oxford uk, isbn 0-19-825079-7. contains turing papers plus draft letter emil post re criticism of turing s convention , , donald w. davies corrections turing s universal computing machine
martin davis (ed.) (1965), undecidable, raven press, hewlett, ny.
emil post (1936), finite combinatory processes—formulation 1 , journal of symbolic logic, 1, 103–105, 1936. reprinted in undecidable, pp. 289ff.
emil post (1947), recursive unsolvability of problem of thue , journal of symbolic logic, vol. 12, pp. 1–11. reprinted in undecidable, pp. 293ff. in appendix of paper post comments on , gives corrections turing s paper of 1936–1937. in particular see footnotes 11 corrections universal computing machine coding , footnote 14 comments on turing s first , second proofs.
turing, a.m. (1936). on computable numbers, application entscheidungs problem . proceedings of london mathematical society. 2 (published 1937). 42: 230–265. doi:10.1112/plms/s2-42.1.230.  (and turing, a.m. (1938). on computable numbers, application entscheidungsproblem: correction . proceedings of london mathematical society. 2 (published 1937). 43 (6): 544–6. doi:10.1112/plms/s2-43.6.544. ). reprinted in many collections, e.g. in undecidable, pp. 115–154; available on web in many places.
alan turing, 1948, intelligent machinery. reprinted in cybernetics: key papers. ed. c.r. evans , a.d.j. robertson. baltimore: university park press, 1968. p. 31. reprinted in turing, a. m. (1996). intelligent machinery, heretical theory . philosophia mathematica. 4 (3): 256. doi:10.1093/philmat/4.3.256. 
f. c. hennie , r. e. stearns. two-tape simulation of multitape turing machines. jacm, 13(4):533–546, 1966.

computability theory

boolos, george; richard jeffrey (1999) [1989]. computability , logic (3rd ed.). cambridge uk: cambridge university press. isbn 0-521-20402-x. 
boolos, george; john burgess; richard jeffrey (2002). computability , logic (4th ed.). cambridge uk: cambridge university press. isbn 0-521-00758-5.  parts have been rewritten burgess. presentation of turing machines in context of lambek abacus machines (cf. register machine) , recursive functions, showing equivalence.
taylor l. booth (1967), sequential machines , automata theory, john wiley , sons, inc., new york. graduate level engineering text; ranges on wide variety of topics, chapter ix turing machines includes recursion theory.
martin davis (1958). computability , unsolvability. mcgraw-hill book company, inc, new york. . on pages 12–20 gives examples of 5-tuple tables addition, successor function, subtraction (x ≥ y), proper subtraction (0 if x < y), identity function , various identity functions, , multiplication.
davis, martin; ron sigal; elaine j. weyuker (1994). computability, complexity, , languages , logic: fundamentals of theoretical computer science (2nd ed.). san diego: academic press, harcourt, brace & company. isbn 0-12-206382-1. 
hennie, fredrick (1977). introduction computability. addison–wesley, reading, mass. qa248.5h4 1977. . on pages 90–103 hennie discusses utm examples , flow-charts, no actual code .
john hopcroft , jeffrey ullman, (1979). introduction automata theory, languages, , computation (1st ed.). addison–wesley, reading mass. isbn 0-201-02988-x.  difficult book. centered around issues of machine-interpretation of languages , np-completeness, etc.
hopcroft, john e.; rajeev motwani; jeffrey d. ullman (2001). introduction automata theory, languages, , computation (2nd ed.). reading mass: addison–wesley. isbn 0-201-44124-1.  distinctly different , less intimidating first edition.
stephen kleene (1952), introduction metamathematics, north–holland publishing company, amsterdam netherlands, 10th impression (with corrections of 6th reprint 1971). graduate level text; of chapter xiii computable functions on turing machine proofs of computability of recursive functions, etc.
knuth, donald e. (1973). volume 1/fundamental algorithms: art of computer programming (2nd ed.). reading, mass.: addison–wesley publishing company. . reference role of turing machines in development of computation (both hardware , software) see 1.4.5 history , bibliography pp. 225ff , 2.6 history , bibliographypp. 456ff.
zohar manna, 1974, mathematical theory of computation. reprinted, dover, 2003. isbn 978-0-486-43238-0
marvin minsky, computation: finite , infinite machines, prentice–hall, inc., n.j., 1967. see chapter 8, section 8.2 unsolvability of halting problem. excellent, i.e. relatively readable, funny.
christos papadimitriou (1993). computational complexity (1st ed.). addison wesley. isbn 0-201-53082-1.  chapter 2: turing machines, pp. 19–56.
hartley rogers, jr., theory of recursive functions , effective computability, mit press, cambridge ma, paperback edition 1987, original mcgraw-hill edition 1967, isbn 0-262-68052-1 (pbk.)
michael sipser (1997). introduction theory of computation. pws publishing. isbn 0-534-94728-x.  chapter 3: church–turing thesis, pp. 125–149.
stone, harold s. (1972). introduction computer organization , data structures (1st ed.). new york: mcgraw–hill book company. isbn 0-07-061726-0. 
peter van emde boas 1990, machine models , simulations, pp. 3–66, in jan van leeuwen, ed., handbook of theoretical computer science, volume a: algorithms , complexity, mit press/elsevier, [place?], isbn 0-444-88071-2 (volume a). qa76.h279 1990. valuable survey, 141 references.

church s thesis

nachum dershowitz; yuri gurevich (september 2008). natural axiomatization of computability , proof of church s thesis (pdf). bulletin of symbolic logic. 14 (3). retrieved 2008-10-15. 
roger penrose (1990) [1989]. emperor s new mind (2nd ed.). oxford university press, new york. isbn 0-19-851973-7. 

small turing machines

rogozhin, yurii, 1998, universal turing machine 22 states , 2 symbols , romanian journal of information science , technology, 1(3), 259–265, 1998. (surveys known results small universal turing machines)
stephen wolfram, 2002, new kind of science, wolfram media, isbn 1-57955-008-8
brunfiel, geoff, student snags maths prize, nature, october 24. 2007.
jim giles (2007), simplest universal computer wins student $25,000, new scientist, october 24, 2007.
alex smith, universality of wolfram’s 2, 3 turing machine, submission wolfram 2, 3 turing machine research prize.
vaughan pratt, 2007, simple turing machines, universality, encodings, etc. , fom email list. october 29, 2007.
martin davis, 2007, smallest universal machine , , definition of universal turing machine fom email list. october 26–27, 2007.
alasdair urquhart, 2007 smallest universal machine , fom email list. october 26, 2007.
hector zenil (wolfram research), 2007 smallest universal machine , fom email list. october 29, 2007.
todd rowland, 2007, confusion on fom , wolfram science message board, october 30, 2007.
olivier , marc raynaud, 2014, programmable prototype achieve turing machines limos laboratory of blaise pascal university (clermont-ferrand in france).

other

martin davis (2000). engines of logic: mathematicians , origin of computer (1st ed.). w. w. norton & company, new york. isbn 0-393-32229-7. 
robin gandy, confluence of ideas in 1936 , pp. 51–102 in rolf herken, see below.
stephen hawking (editor), 2005, god created integers: mathematical breakthroughs changed history, running press, philadelphia, isbn 978-0-7624-1922-7. includes turing s 1936–1937 paper, brief commentary , biography of turing written hawking.
rolf herken (1995). universal turing machine—a half-century survey. springer verlag. isbn 3-211-82637-8. 
andrew hodges, alan turing: enigma, simon , schuster, new york. cf. chapter spirit of truth history leading to, , discussion of, proof.
ivars peterson (1988). mathematical tourist: snapshots of modern mathematics (1st ed.). w. h. freeman , company, new york. isbn 0-7167-2064-7. 
roger penrose, emperor s new mind: concerning computers, minds, , laws of physics, oxford university press, oxford , new york, 1989 (1990 corrections), isbn 0-19-851973-7.
paul strathern (1997). turing , computer—the big idea. anchor books/doubleday. isbn 0-385-49243-x. 
hao wang, variant turing s theory of computing machines , journal of association computing machinery (jacm) 4, 63–92 (1957).
charles petzold, petzold, charles, annotated turing, john wiley & sons, inc., isbn 0-470-22905-5
arora, sanjeev; barak, boaz, complexity theory: modern approach , cambridge university press, 2009, isbn 978-0-521-42426-4, section 1.4, machines strings , universal turing machine , 1.7, proof of theorem 1.9
kantorovitz, isaiah pinchas (december 1, 2005). note on turing machine computability of rule driven systems . sigact news. acm. 36 (4): 109–110. doi:10.1145/1107523.1107525. retrieved april 6, 2014. 
kirner, raimund; zimmermann, wolf; richter, dirk: on undecidability results of real programming languages , in 15. kolloquium programmiersprachen und grundlagen der programmierung (kps 09), maria taferl, austria, oct. 2009.