A Turing Machine that is deterministic, i.e. that for every state and symbol, there is ONE action the machine will do. Its transition function is deterministic.

A DTM is defined by a 7-tuple: (Q, E, L, d, qstart, qaccept, qreject), where:

  1. Q is the set of states
  2. E is the input alphabet, not containing the symbols '_' (space) and ">" (beginning of the tape).
  3. L is the tape alphabet, so L = E U {_} U {>}.
  4. d is the transition function. d: Q * L -> Q * L * {L,R}, where L and R indicate the head moves left or right, respectively.
  5. qstart, qaccept and qreject are memebers of Q

See also Non Deterministic Turing Machine.

Log in or register to write something here or to contact authors.