Lecture 19 (NTMs and Enumerators), 11/01/05

Concepts, definitions (in italics):

• Deterministic vs. non-deterministic TMs
• Computational tree for non-deterministic computation
• Simulating nondeterministic TMs with regular TMs
• Theorem: L is recognizable (decidable) by an NTM if and only if it is recognizable (decidable) by a regular TM.
• An enumerator of a language: no input, just a button to push, and then the language gets enumerated as output. Note that there is no specific order prescribed for the enumerated strings.
• Enumerating a set or a language: for ANY member element, we know that it will be printed out within some finite time period.
• The definition of an enumerable language: one for which an enumerator exists.
• Theorem: L is enumerable if and only if it is recognizable.

Reading:

• Chapter 3 finish, except for proof of Theorem 3.21

Skills:

• Know new definitions, understand new concepts.
• What do the nodes and edges in an NTM computational tree correspond to? Which is the root? leaves?
• What are the children for a given node of a computational tree?  What do all the nodes at depth k of the tree correspond to?
• How to determine the address of a node in an NTM computational tree?
• Given the initial configuration and the address of some node x, how to compute the configuration at x?
• Understand the proof for first theorem above.
• What are the two parts of the proof of the second theorem above?

Notes:

• Because of the Church-Turing thesis, it's enough to describe a TM algorithmically (in pseudocode).
• We saw two examples of non-deterministic algorithms: deciding if n is a prime, and deciding if there is a path in a graph G from s to t.
• Computation trees can be defined for any non-deterministic computation (of NFAs, PDAs, NTMs). Beware: Computation trees are very different from parse trees!
• The tree is a description of all the computational possibilities of some specific machine on some specific input.  The actual computation is a single path in that tree, from the root down.
• Examples of enumerating: naturals, integers, pairs of naturals, pairs of integers, (tuples of integers), S*.
• The second theorem can be restated as: the set of enumerable languages is the same as the set of recognizable languages.