Тјурингова_машина
Наводи
Martin Davis (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY. Martin Davis (2000). Engines of Logic: Mathematicians and the origin of the Computer, 1st edition, W. W. Norton & Company, New York. ISBN 0-393-32229-7 pbk.. Hennie, Fredrick (1977). Introduction to Computability. Addison-Wesley, Reading, Mass. . On pages 90–103 Hennie discusses the UTM with examples and flow-charts, but no actual 'code'. Rolf Herken. The Universal Turing Machine – A Half-Century Survey. Springer Verlag. ISBN 3-211-82637-8. 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. John Hopcroft and Jeffrey Ullman, (1979). Introduction to Automata Theory, Languages and Computation, 1st edition, Addison-Wesley, Reading Mass. ISBN 0-201-02988-X.. A difficult book. Centered around the issues of machine-interpretation of "languages", NP-Completeness, etc. Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation, 2nd ed., Reading Mass: Addison-Wesley. 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. Knuth, Donald E. (1973). Volume 1/Fundamental Algorithms: The Art of computer Programming, 2nd ed., Reading, Mass.: Addison-Wesley Publishing Company. . 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 Bibliographypp. 456ff. 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. Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1. Chapter 2: Turing machines, pp. 19 – 56. Emil Post (1936), "Finite Combinatory Processes - Formulation 1", Journal of Symbolic Logic, 1, 103-105, 1936. Reprinted in The Undecidable pp. 289ff. Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic, vol. 12, pp. 1–11. Reprinted in The Undecidable pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936-7. Roger Penrose (1989, 1990). The Emperor's New Mind, 2nd edition, Oxford University Press, New York. ISBN 0-19-851973-7. Ivars Peterson (1988). The Mathematical Tourist: Snapshots of Modern Mathematics, 1st edition, W. H. Freeman and Company, New York. ISBN 0-7167-2064-7 (pbk.). Rogozhin, Yurii, "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) Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 3: The Church-Turing Thesis, pp. 125 – 149. Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures, 1st ed., New York: McGraw-Hill Book Company. ISBN 0-07-061726-0. Paul Strathern. Turing and the Computer – The Big Idea. Anchor Books/Doubleday. ISBN 0-385-49243-X. Alan Turing (1936), "On Computable Numbers, With an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Eprint. Reprinted in The Undecidable pp. 115–154. 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. Hao Wang, "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63-92 (1957). Stephen Wolfram, Wolfram, Stephen, A New Kind of Science, Wolfram Media, ISBN 1-57955-008-8