Deterministic Turing Machine

computation

Definition

Deterministic Turing Machine

A Turing machine $M$ is called deterministic, if for all $(q,X)\in Q\times \Gamma$ there exists at most one element $(q,X;p,Y,D)\in \delta$, i.e.:

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

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