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]