Turing Machines

Overview

A Turing machine is a $7$ -tuple $⟨ Q, Σ, Γ, δ, q_{0}, q_{a}, q_{r} ⟩$ , where $Q$ , $Σ$ , and $Γ$ are finite sets and:

$Q$ is the set of states,
$Σ$ is the input alphabet not containing the blank symbol $␣$ ,
$Γ$ is the tape alphabet where $␣ \in Γ$ and $Σ \subseteq Γ$ ,
$δ : Q \times Γ \to Q \times Γ \times {L, R}$ is the transition function,
$q_{0} \in Q$ is the start state,
$q_{a}$ is the accept state, and
$q_{r}$ is the reject state, where $q_{r} \neq q_{a}$ .

A language is Turing-recognizable (also known as recursively enumerable or semidecidability) if a Turing machine recognizes it. Otherwise it is Turing-unrecognizable. A language is co-Turing-recognizable if it is the complement of a Turing-recognizable language. An analogous definition holds for co-Turing-unrecognizable.

Configurations

A configuration of a Turing machine $M$ refers to $M$ 's current state, current tape contents, and current head location. For a state $q$ and strings $u$ and $v$ over tape alphabet $Γ$ , we write $u q v$ for the configuration where the current state is $q$ , the current tape contents is $u v$ , and the current head location is the first symbol of $v$ . A few configurations are notable:

The starting configuration on input $w$ is $q_{0} w$ .
An accepting configuration is a configuration with the accept state.
A rejecting configuration is a configuration with the reject state.
A halting configuration is either an accepting configuration or rejecting configuration.

We say configuration $C_{1}$ yields configuration $C_{2}$ if the Turing machine in question can reach $C_{2}$ from $C_{1}$ in a single step.

A Turing machine $M$ accepts input $w$ if a sequence of configurations, beginning with the starting configuration and ending in an accepting configuration, exists.

Computation Histories

Let $M$ be a Turing machine and $w$ an input string. An accepting computation history for $M$ on $w$ is a sequence of configurations, $C_{1}, C_{2}, \dots, C_{n}$ , where:

$C_{1}$ is the start configuration of $M$ on $w$ ,
$C_{n}$ is an accepting configuration of $M$ , and
each $C_{i}$ legally follows from $C_{i - 1}$ according to the rules of $M$ .

A rejecting computation history is defined analogously.

Tableaus

Let computation history $H$ be a sequence of configurations $C_{1}, C_{2}, \dots, C_{n}$ . A tableau of $H$ is a visualization of $H$ arranged in a table. Configuration $C_{i}$ is listed in the tableau's $i^{th}$ row. The $j^{th}$ column of the $i^{th}$ row corresponds to the $j^{th}$ symbol in $C_{i}$ .

An accepting tableau is a tableau corresponding to an accepting computation history. A rejecting tableau is a tableau corresponding to a rejecting configuration history.

Dovetailing

Dovetailing refers to the simulation of two or more Turing machines in parallel on a single Turing machine. Typically it is implemented by simulating one step of each machine at a time.

In the case of infinitely many TMs, dovetailing is typically accomplished by running the first machine for one step, the first two machines for two steps, the first three machines for three steps, and so on and so forth.

Closure Operations

Let $A$ and $B$ be Turing-recognizable languages. Such languages are closed under the following:

Union: $A \cup B$
Intersection: $A \cap B$
Concatenation: $A \circ B$
Kleene Star: $A^{*}$

Model Independence

A computation model's invariance to certain changes is known as its robustness. The Turing machine is an especially robust computing model - no variation of the model is known to increase the recognizing power of the Turing machine. In addition, seemingly distinct computation models (e.g. lambda calculus) were proven to be equivalent in power.

Multi-tape

A multi-tape Turing machine is a Turing machine with several tapes. Each tape has its own head for reading and writing, with the initial input set on the first tape and other tapes starting blank. A multi-tape Turing machine with $k$ tapes has transition function:

δ : Q \times Γ^{k} \to Q \times Γ^{k} \times {L, R}^{k} .

Multi-tape Turing machines are equivalent in power to a ordinary Turing machines.

Nondeterministic

A nondeterminstic Turing machine (NTM) is a Turing machine that allows ambiguous transitions from a given state. At any point in computation, the machine may proceed according to several possibilities. An NTM has transition function:

δ : Q \times Γ \to P (Q \times Γ \times {L, R}) .

Nondeterministic Turing machines are equivalent in power to ordinary Turing machines. They are deciders if every branch of computation halts.

Enumerators

An enumerator is a variant of a Turing machine. Like a Turing machine, it has an infinite tape and a finite state control. Unlike a Turing machine, it also has a printer as an output device for printing strings. It begins with a blank input tape and prints the strings, one at a time, in its corresponding language.

Enumerators are equivalent in power to Turing machines.

Church-Turing Thesis

By virtue of model independence, the Church-Turing thesis states that a problem has an effective method if and only if it is computable by a Turing machine. The thesis aims to formalize what an effective method (i.e. an algorithm) is.

Self-Reproduction

In the context of Turing machines, we can build a programming/quine with the aid of a quotation function. This is a computable function $q : Σ^{*} \to Σ^{*}$ , where if $w$ is any string, $q (w)$ is the description of a TM $P_{w}$ that prints out $w$ and then halts.

The quine is denoted $S E L F$ and consists of template $A$ and action $B$ given as:

$A$ = $P_{⟨ B ⟩}$ , i.e. the TM that prints out $B$ .
$B$ = "On input $⟨ M ⟩$ , where $M$ is a portion of a TM:
1. Compute $q (⟨ M ⟩)$ (which is $A$ when $⟨ M ⟩ = ⟨ B ⟩$ ).
2. Combine the result with $⟨ M ⟩$ to make a complete TM.
3. Print the description of this TM and halt."

Kleene's Recursion Theorem

Let $T$ be a TM that computes a function $t : Σ^{*} \times Σ^{*} \to Σ^{*}$ . Then there exists is a TM $R$ that computes a function $r : Σ^{*} \times Σ^{*}$ , where for every $w$ ,

r (w) = t (⟨ R ⟩, w) .