**Lecture 17
(Nondeterministic TMs), 11/1/17**

**Concepts, definitions (in
italics):**

*Nondeterministic*Turing Machine (NTM)*Computational tree*for computation of NTM M**on input w**- Analogue
of computational path for regular TMs

·
The tree **T _{M,w}**

- Nodes
= configurations, edges = transitions
- Root
= initial computation

·
In an NTM, there can be multiple distinct
transitions from a given (state, char), with a separate child in the tree for
each one.

- NTM M is said to
*accept*w if there exists a path in the computational tree which leads to an accepting configuration - NTM M is said to
*reject*w if every path in the computational tree leads to a rejecting configuration - Otherwise (there is no
accept state and not every path terminates) we say that M does not
terminate on M.

·
Computation trees can be defined for any
non-deterministic computation (for NFAs, PDAs, NTMs).

Beware: For CFGs, computation trees are very different from parse trees!

*Node addresses for nodes in the computational tree**Length of address = depth of corresponding node = # of transitions from initial configuration to this one**Each digit in address = number of transition to take next**Enumerating the addresses in**Breadth-First**order**Theorem*: For every NTM, there exists an equivalent TM (that accepts/rejects/non-terminates on the same inputs)*The notion of enumeration*- Simulating a Nondeterministic Turing Machine with a
regular (multitape) TM
- On one tape, enumerate all
node addresses in
*Breadth-First**order* *For each address, use another tape to compute the configuration of the corresponding order, by following the path from the root**Accept if we hit an accepting configuration; reject if we have traversed the whole tree (reached rejecting configuration at the end of every path)**Corollary*: A language L is recognizable (decidable) by an NTM if and only if it is recognizable (decidable) by a regular TM.

**Reading:**

· Chapter 3 through corollary 3.19

**Skills:**

- Know new definitions,
understand new concepts.
- What is the transition function
like for a Nondeterministic Turing Machine?
- What do the
*nodes*in an NTM computational tree correspond to? Which is the*root*? What are leaves? - What do the
*edges*in an NTM computational tree correspond to? What are the*children*for a given node of a computational tree? What is a path? - Given an NTM
**M**and an input string**w**and an address string**a**= “a_{1}a_{2}… a_{k}”, figure out the configuration of**M**at address**a,**when computing over**w**

**Notes:**