3 Turing Machines

Deterministic TMs are seen in the Computability Theory Cheat Sheet.

3.1 K-tapes Turing Machines

Let \(k \geq 1\) be the number of tapes. A k-tape TM is a quadruple \((Q, \Sigma , \delta , q_0)\). Special symbols \(\# , \triangleright , \in \Sigma \), while \(L,R,- \notin \Sigma \). Since we are only considering decision problems, \(\mathrm{YES},\mathrm{NO}\notin Q\) are the halting states. The transition function differs but is subject to the same restrictions as a classical TM.

\[ \delta : Q \times \Sigma ^k \to Q \cup \{ \mathrm{YES}, \mathrm{NO}\} \times (\Sigma \times \{ L, R, -\} )^k \]

3.2 IO Turing Machines

Are useful to study space complexity. Any k-tape TM \(M = (Q, \Sigma , \delta , q_0)\) is of IO type \(\Leftrightarrow \delta \) is subject to the following constraints. Consider \(\delta (q_1, \sigma _1, \hdots , \sigma _k) = (q', (\sigma _1', D_1), \hdots , (\sigma _k', D_k))\)

\(\sigma _1' = \sigma _1\)	First tape is read-only
\(D_k = R\) or \((D_k = -) \Rightarrow \sigma '_k = \sigma _k\)	Last tape is write-only
\(\sigma _1 = \# \Rightarrow D_1 \in \{ L, -\} \)	Input tape is right-bounded

3.3 Nondeterministic Turing Machines

A nondeterministic TM is a quadruple \(N = (Q, \Sigma , \Delta , q_0)\) where \(Q, \Sigma , q_0\) are the same as in other turing machines. They can be of IO and k-tape type. The difference rilies in the fact that

\[ \Delta \subseteq (Q \times \Sigma ) \times ((Q \cup \{ \mathrm{YES}, \mathrm{NO}\} ) \times \Sigma \times \{ L,R, -\} ) \]

Is not a transition function but a transition relation. The same syntax as for other TMs is used for nondet. TMs configurations and computations. A nondeterministic TM \(N\) decides \(I\) if and only if \(x \in I \Leftrightarrow \) there exists at least a computation such that \((q_0, \underline{\triangleright }, x, \triangleright , \hdots , \triangleright ) \to ^*_N (\mathrm{YES}, w_1, \hdots , w_k)\)

Note

A single computation on a nondeterministic TMs is not a tree. Many computations together, can be arranged in a tree.

The degree \(d\) of nondeterminism of a NDTM \(N = (Q, \Sigma , \Delta , q_0)\) can now be defined as \(d = \max \{ \deg {(q,\sigma )} \mid q \in Q, \sigma \in \Sigma \} \), where \(\text{deg}(q, \sigma ) = \# \{ (q', \sigma ', D) \mid ((q, \sigma ), (q', \sigma ', D)) \in \Delta \} \)