Turing Machine

A Turing machine (TM) is a tuple $$M=(Q, \Sigma, \delta)$$ where

• $$Q$$ is a finite set of states, containing a start state $$q_0$$, an accepting state $$q_{y}$$, and a rejecting state $$q_{n}$$. The states $$q_{y}$$ and $$q_{n}$$ are distinct.
• $$\Sigma$$ is the alphabet which is a collection of symbols, containing a special blank symbol $$\bot$$. The input does not contain the blank symbol $$\bot$$.
• $$\delta$$ is a transition function from $$Q\times \Sigma$$ to $$Q\times \Sigma \times \{\leftarrow,\rightarrow, -\}$$.

In its physical implementation, a Turing machine has a tape, a cursor, a state register, and a lookup table for transitions. The tape is divided into cells and initialized with blank symbols; we assume it extends infinitely at both ends. At the beginning, the tape contains the input string, the cursor locates at the first input symbol, and the machine starts with state $$q_0$$. At each step, given the current state $$q$$ and the symbol $$a$$ at the cursor, the machine follows the transition rule $$\delta(q, a) = (q’, b, d)$$ by changing to state $$q’$$, overwriting the cell at the cursor with $$b$$, and moving the cursor in the direction $$d$$.

Given a TM and an input string, a configuration describes the running context of the machine. Formally, a configuration is a tuple $$(q, u, w)$$, where $$q$$ is the current state, $$u$$ is the string to the left the cursor, and $$w$$ is the string to the right of the cursor.

We say a configuration $$c$$ yields another configuration $$c’$$ if the machine moves one step from $$c$$ to $$c’$$. A TM $$M$$ accepts an input string $$x$$ if and only if there exists a sequence of configurations $$c_0, c_1, \ldots, c_n$$ such that $$c_0$$ is the start configuration, $$c_i$$ yields $$c_{i+1}$$ for $$0 \leq i \leq n-1$$, and $$c_n$$ is a configuration with the accepting state.

The language of a Turing machine $$M$$ is $$L(M)= \{w\in\Sigma^\star \mid M \hbox{ accepts } w\}$$. Given an input, a TM may accept it, reject it, or run forever.

A language $$L$$ is recursively enumerable (Turing-recognizable) if there is a Turing machine $$M$$ recognizes it, that is, $$M$$ accepts strings in $$L$$, but either rejects or runs forever for strings not in $$L$$. A language $$L$$ is recursive (Turing-decidable) if there is a Turing machine $$M$$ decides it, that is, $$M$$ accepts strings in $$L$$ and rejects strings not in $$L$$ (it halts on every input).

The running time of a TM $$M$$ on input $$x$$, denoted by $$t_M(x)$$, is the number of steps $$M$$ takes on input $$x$$ before halting ($$M$$ may not halt). A TM $$M$$ is time bounded by $$f\colon N \to N$$ if $$M$$ halts within $$f(|x|)$$ steps for any input $$x$$, that is $$\forall x [ t_M(x)\leq f(|x|)]$$.

A multitape Turing Machine extends a TM with multiple tapes and the input is on the first tape, with others blank. The transition function $$\delta$$ is defined from $$Q\times \Gamma^k$$ to $$Q\times \Gamma^k \times \{\leftarrow, \rightarrow, -\}^k$$, where $$k$$ is the number of tapes. Every multi-tape TM can be simulated by an equivalent single tape TM with quadratic slowdown. For any $$k$$-tape Turing machine running in time $$t(n)$$, there is an equivalent one-tape Turing machine running in time $$O(t(n)^2)$$.

A nondeterministic Turing Machine extends a TM with several possibilities in each step of computation.
The transition function $$\delta$$ is defined from $$Q\times \Gamma$$ to $$2^{Q\times \Gamma \times \{\leftarrow, \rightarrow, -\}}$$. Every nondeterministic Turing Machine has an equivalent deterministic Turing machine.

The Church-Turing thesis says that there exists languages that are not Turing-recognizable. This is because the set of all TMs is countable, but the set of all languages is uncountable.

The halting problem is to decide whether a TM accepts an input.
$HALT = \{(M, w) \mid M \hbox{ is a TM and } M \hbox{ accepts } w \}.$
HALT is undecidable, but Turing-recognizable.

A language $$L$$ is decidable if and only if both $$L$$ and its complement $$\overline{L}$$ are Turing-recognizable.

The complement language of HALT is not Turing-recognizable.