CSE 111, Fall 2004

Great Idea II:

Turing Machines

(Click on the title above to do a Google search.)

Last Update: 1 November 2004

Note: NEW or UPDATED material is highlighted

II. Turing's Insight.

Every algorithm can be expressed in a language for a computer (viz., a Turing machine) consisting of an arbitrarily long paper tape divided into squares (like a roll of toilet paper, except you never run out), with a read/write head, whose only nouns are "0" and "1", and whose only verbs (or basic instructions) are:

  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.

  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.

  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).

  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).

  8. To find out more about Alan Turing, go to these websites first:

    or read his biography:

    or see the play:

    NEW or read this article from 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.

Copyright © 2004 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 111F04/greatidea2-2004-11-01.html