Up to ReadingRoom

Each of the theory textbooks has a good section on Turing Machines. In class on 16 Nov we will be covering TMs as automata. On 19 Nov we will be covering universality and undecidability (including diagonalization and the halting theorem).

The following table provides a key to which parts of which theory books cover these topics.

• 	16 November		19 November
  	TM as automaton	optional automaton material	universal TM and decidability	optional decidability material
  Sipser	chapter 3		Chapter 4	Chapters 5, 6
  Hopcroft, Motwani, and Ullman	Sections 8.2, 8.4, 8.5 and enough background to make sense of this	Sections 8.3, 8.6	Section 8.1, 9.1, 9.2	remainder of chapter 9
  Lewis and Papadimitriou	Chapter 4 through 4.5	remainder of chapter 4	chapter 5 through 5.3	remainder of chapter 5

Additional resources on Turing Machines (relatively triaged):

• Turing machine, vague overview

• Wikipedia: Turing Machine

• Stanford Encyclopedia of Philosophy: Turing Machines. In-depth coverage of basics and more advanced topics including the halting problem, busy beaver, computability, and more

• Wolfram Mathworld article(short). Nice diagram of the process, some cool cross-reference topics.

Finally, JFLAP supports TMs.