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, Σ, δ, q_{0})$ . Special symbols $#, ▹, \in Σ$ , while $L, R, - \notin Σ$ . Since we are only considering decision problems, $YES, NO \notin Q$ are the halting states. The transition function differs but is subject to the same restrictions as a classical TM.

δ : Q \times Σ^{k} \to Q \cup {YES, NO} \times (Σ \times {L, R, -})^{k}

3.2 IO Turing Machines

Are useful to study space complexity. Any k-tape TM $M = (Q, Σ, δ, q_{0})$ is of IO type $\Leftrightarrow δ$ is subject to the following constraints. Consider $δ (q_{1}, σ_{1}, \hdots, σ_{k}) = (q^{'}, (σ_{1}^{'}, D_{1}), \hdots, (σ_{k}^{'}, D_{k}))$

$σ_{1}^{'} = σ_{1}$	First tape is read-only
$D_{k} = R$ or $(D_{k} = -) \Rightarrow σ_{k}^{'} = σ_{k}$	Last tape is write-only
$σ_{1} = # \Rightarrow D_{1} \in {L, -}$	Input tape is right-bounded

3.3 Nondeterministic Turing Machines

A nondeterministic TM is a quadruple $N = (Q, Σ, Δ, q_{0})$ where $Q, Σ, 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

Δ \subseteq (Q \times Σ) \times ((Q \cup {YES, NO}) \times Σ \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}, \underset{―}{▹}, x, ▹, \hdots, ▹) \to_{N}^{*} (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, Σ, Δ, q_{0})$ can now be defined as $d = max {\deg (q, σ) ∣ q \in Q, σ \in Σ}$ , where $deg (q, σ) = # {(q^{'}, σ^{'}, D) ∣ ((q, σ), (q^{'}, σ^{'}, D)) \in Δ}$