Deterministic Turing Machine (DTM)
 Gist:
Deterministic TM makes no more than one move from any configuration.
Definition: Let M = (Q, S, G, R, s, F) be a TM. M is a deterministic TM if for each rule pa ® qbt Î R it holds that R – {pa ® qbt} contains no rule with the left-hand side equal to pa.
19/45
Theorem: For every TM M, there is an equivalent         DTM Md.
Proof: See page 634 in [Meduna: Automata and Languages]