Great Idea II:

Turing Machines

II. Turing's Insight.

1. move-left-1-square
2. move-right-1-square
3. print-0-at-current-square
4. print-1-at-current-square
5. erase-current-square

1. The paper that started it all:

   Turing, Alan M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Ser. 2, Vol. 42: 230-265.

   • Reprinted, with corrections, in Martin Davis (ed.), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (New York: Raven Press, 1965): 116-154.

   • The on-line version above is best read using Microsoft Internet Explorer (or any other browser that uses cascaded style sheets).
   • Warning: The on-line version has several typographical errors!

   • another online version!

   ---

2. The formulation of Turing Machines that we are using in CSE 111:

   Rapaport, William J. (1985), "Turing Machines" [PDF], from Morton L. Schagrin, Randall R. Dipert, & William J. Rapaport, Logic: A Computer Approach (New York: McGraw-Hill, 1985): 327-339.

   • Our notation for TM tapes [PDF]
   • TM Program for Conjunction
   • TM flowchart for palindrome problem (from lecture)
   • Ed's Brain: The Flowchart (humor)

   ---

3. A good survey, with excellent links to further information:

   Barker-Plummer, David; & the Editors of the SEP (2003), "Turing Machine", in Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy (Summer 2003 Edition).

4. Weizenbaum, Joseph (1976), Computer Power and Human Reason (New York: W.H. Freeman).
   • Ch. 2 ("Where the Power of the Computer Comes From") contains a masterful presentation of a Turing Machine implemented with pebbles and toilet paper!
   • This is also an excellent book on the role of computers in society, by the creator of the "Eliza" program.

5. Suber, Peter (1997), "Turing Machines" (a 2-part handout; click on "second hand-out" at the end of part I to get to part II).

6. Weintraub, Steven (2004), "Turing Machines".

7. Dewdney, A.K. (1989), "Algorithms: Cooking Up Programs", "Turing Machines: The Simplest Computers", and "Universal Turing Machines: Computers as Programs", Chs. 1, 28, & 48 from Dewdney's The Turing Omnibus: 61 Excursions in Computer Science (Rockville, MD: Computer Science Press).
   • Included primarily for Ch. 48 on Universal Turing Machines, with the earlier chapters included for the sake of completeness.

8. To find out more about Alan Turing, go to these websites first:
   • Hodges, Alan, "Alan Turing"
   • Copeland, Jack, " The Turing Archive for the History of Computing"
     • See especially:
       Copeland, Jack (2000), "What Is a Turing Machine?"

   or read his biography:

   • Hodges, Alan (2000), Alan Turing: the Enigma (revised edition) (New York: Walker and Co.).
     • Reviewed by:
       Douglas R. Hofstadter, "Mind, Body and Machine", New York Times Book Review (13 November 1983).

     • Reviewed by:
       Stephen Toulmin, "Fall of a Genius", New York Review of Books (19 January 1984): 3-4,6.
       • See also: Stern, Howard; & Daston, Lorraine (1984), "Turing and the System" (letter to the editor, with Toulmin's reply), New York Review of Books (26 April): 52-53.

     • Reviewed by:
       Jeremy Bernstein, "A Portrait of Alan Turing", The New Yorker (20 January 1986): 78,81-87.

   or see the play:

   • Whitemore, Hugh (1986), "Breaking the Code"
     • An excerpt appeared as:
       Whitemore, Hugh (1988), "The Enigma: Alan Turing Confronts a Question of Right and Wrong", The Sciences (March-April): 40-41.

   or read this article from Business Week:

   • Reinhardt, Andy (2004, May 10), "Alan Turing: Thinking Up Computers", Business Week

9. Just for fun:
   Stewart, Ian (1994), "Mathematical Recreations: A Subway Named Turing", Scientific American (September): 104,106-107.

10. Rather more advanced:
    Curtis, M.W. (1965), "A Turing Machine Simulator", Journal of the Association for Computing Machinery 12(1) (January): 1-13.