Lecture 16 (TM languages), 3/22/06

Concepts, definitions (in italics):

• Formal definition of a Turing machine
• Initial/Final configurations for TM computations
• Textbook notation (format) for TM configuration
• A language of a TM = set of strings it accepts
• Turing recognizable language = language of some TM
• Turing decidable language L = language of some TM, where all w not in L are rejected
• Church-Turing Thesis

Reading:

• Chapter 3.3 to end of p.155
• Chapter 3.1 continue

Skills:

• Convert between a triple-based representation of a configuration and the book's format
• Understand the difference between a decidable and a recognizable language; why the set of Turing-decidable languages is a subset of the set of Turing-recognizable languages.

Notes:

• There was no distinction between deciding and recognizing (we called it all "accepting") before, because machines that never terminate were not an issue. For Turing Machines, this IS an issue.
• We will prove that the halting problem is undecidable; from the Church-Turing Thesis, it follows that there exists no algorithm that will solve it correctly for all inputs.
• We will prove that the set of CF languages is a strict subset of Turing-decidable languages, that the set of Turing-decidable languages is a strict subset of Turing-recognizable languages, and that some languages are non-recognizable.