Lecture 15 (Turing Machine Intro), 3/20/06

Concepts, definitions (in italics):

• Turing machines (TMs): what they consist of
• TM transitions: what they consist of
• TM configurations: what they consist of
• Blanks are part of the tape alphabet but not of input alphabet; initially, all cells right of input string are blanks.
• Initial configuration for TM computations.
• 2 halting states: accept, reject
• Every TM computation either halts (accepts or rejects) or goes into an infinite loop.
• Halting problem: Given a description of a TM M and input string w, will M halt on w?
• Church-Turing Thesis: if a function (from strings to strings or from strings to booleans) is computable, it can be computed by some TM.

Reading:

• Start chapter 3.1

Skills:

• Know new definitions, understand new concepts.
• Given a configuration and the transitions, what is the next configuration?
• What does it mean that a TM accepts a string? rejects a string?

Notes:

• While the TM tape is infinite, its contents at any point is finite (followed by infinitely many blanks).
• If on first cell, a TM will just stay there instead of moving left.
• TMs can also act to compute functions, where they accept all inputs and leave the output string on the tape when done.