Deterministic Turing Machine

Definition

Deterministic Turing Machine

A deterministic Turing machine is a Turing machine whose transition relation assigns at most one move to every state–symbol pair:

$$\forall (q,X)\in Q\times \Gamma :\left|\{(q,X;p,Y,d)\in \delta \}\right|\le 1.$$

Such a relation is a partial function, denoted

$$\delta (q,X)=(p,Y,d),d\in D=\{L,R,S\}.$$

Every configuration of $M$ has at most one successor, so the computation on an input is a single path. The machine accepts an input if that path reaches an accepting state $q\in F$.

The definition is the special case of the nondeterministic Turing machine obtained by requiring at most one move per state–symbol pair.