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

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.