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

Concepts, definitions (in italics):

         The tree TM,w is a description of all the computational possibilities of some specific machine M on some specific input w.  The actual computation is a single path in that tree, from the root down.

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

         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!

 

Reading:

         Chapter 3 through corollary 3.19  

Skills:

Notes: