CH 4 - Turing Machines Flashcards
1
Q
Define a Turning Machine.
A
2
Q
Define a configuration. What are the inital and halting configurations?
When does a TM accept/reject an input word?
Define a language L(M) that is recognised by a TM. What does it mean for a language to be Turing recognisable?
A
3
Q
Define a decider TM.
Define time complexity/ run time f(n).
Define O(n^k).
A
4
Q
State and prove a lemma on f and g in O(n^k).
Define the complexity class DTime(O(n^k)).
State a Lemma on regular languages and complexity.
A
5
Q
Lemma: tape when halting, running time.
Define equivalent TM’s M_1 and M_2.
State a lemma on equivalent TM’s.
A
6
Q
Define a multitape Turing machine.
State a theorem on multi vs single tape TM’s.
A
7
Q
Define a nondeterministic Turning machine.
State a theorem on nondeterministic vs deterministic TM’s.
A
