/
Deterministic Turing Machine (DTM)

Deterministic Turing Machine (DTM)

Sept 13, 2021

In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation. In contrast to Non-Deterministic Turing Machine (NTM) which allows more than 1 action.

A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things:

  • the symbol to be written to the tape,
  • the direction (left, right or neither) in which the head should move, and
  • the subsequent state of the finite control.

For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5.