Equivalence of Turing Machine Models Flashcards
1
Q
What Turing machine variants can a basic Turing machine simulate?
A
- stay or move action
- insert/delete memory
- k-memories
- nondeterministic TM
All of these run in polynomial time except the nondeterministic TM variant
