A Turing Machine is a tuple $(\mathcal{X},\mathcal{Q},\Gamma ,q_i,F,\delta )$ where:

• $\mathcal{X}$ is an alphabet (finite set of atomic symbols)
• $\mathcal{Q}=\{q_0,q_1,\dots ,q_n\}$ is a finite set of states
• $\Gamma$ is the set of symbols that can be stored on the tape (we assume $\{\circ ,\bullet \}\subseteq \Gamma$)
• $q_i\in \mathcal{Q}$ is the initial state
• $F=\{q_{\text{accept}},q_{\text{reject}}\}\subseteq \mathcal{Q}$ are terminating states
• $\delta :\mathcal{Q}\times \Gamma \to \mathcal{Q}\times \Gamma \times \{L,R\}$ is the transition function

The transition function maps a (state, symbol) to (state, symbol, direction). The direction tells us which way the head must be moved.

Initially the tape stores the input word, the head in the first symbol of the input string, and the machine in the state $q_i$.

As the computation proceeds, the situations of the machine (or configuration) is described by a triple of: the current state, contents of the state, and the position of the head in the tape.

The word is accepted if the TM reaches $q_{\text{accept}}$ and rejected if it reaches $q_{\text{reject}}$. Machine can also loop forever.

Example

The following machine recognises the language $\{1^{2^n}|n\ge 0\}$, that is, the language of strings that contain a number of $1$s which is a power of $2$.

Informal description:

1. If head is on blank when we start, reject.
2. Starting on first $q$, move to end of string (first blank symbol), changing every other $1$ into $\bullet$.
3. If tape contained just one $1$, accept.
4. If the number of $1$s was odd, reject.
5. Return head to beginning of input.
6. Repeat.

The idea is that each iteration changes half of the $1$s into $\bullet$. If the number of ones is a power of $2$, we will eventually end up with just one $1$ and accept the input.

Power of TM

TMs are strictly more powerful than PDA. TMs can be associated with Type-0 languages in the Chomsky hierarchy. These are called recursively-enumerable languages.

However there are languages that are not recognisable, even by a TM. (The Halting Problem)

TMs as partial functions

TMs implement partial functions, they map words to (word, boolean) tuples. Since TMs can get caught in continuous loops, it’s possible for a TM to not return an output for a given word. (hence why they are only partial functions)

Turing computable

A function that can be implemented by a TM is called Turing computable.

Link to original

TMs are the theoretical basis of imperative programming.

Variants of Turing Machines

• Non-deterministic transitions: transition function returns a set: for the same state / symbol read, there may be several alternative transitions. One of them will be chosen non-deterministically.
• Multiple tapes: machine may have several tapes and corresponding read / write heads. Transition function defines which is the next state, depending on tuple of symbols read on the tapes, and indicates which symbol should be written in each tape.
• Tape with starting point, but unlimited to the right.
• Instead of a tape where it is possible to read and write, one can define a reading tape (for inputs), writing tape (for outputs) and a working tape (for r/w).

All these variants of TMs are computationally equivalent.

Universal TM

The Universal Turing Machine is a Turing machine that is capable of reading the “code” of a Turing machine along with its input, and simulates the execution of the machine on this input.

To do this, we need a way to ‘encode’ TMs.

• We can encode a TM on to a tape:
• This allows a TM $U$ to take another TM $A$ as input.
  • $U$ can simulate $A$
  • $U$ can attempt to establish properties of $A$ (e.g. if it halts)
  • $U$ is called the Universal Turing Machine

Encoding Turing Machines

We can give a code to each Turing machine.

• Assume the machine has $n$ states $q_0,\dots ,q_{n-1}$, where each $q_i$ is a number, $q_0$ is the initial state, and the last $m$ states are final.
• Assume the input alphabet is $\{1\}$ and the tape alphabet is $\{0,1\}$ ($0$ is the blank symbol). A binary alphabet is sufficient to encode any kind of data.
• The transition function is represented as a table, or equivalently a list of $5$-tuples of the form $(q,s,q^{\prime },s^{\prime },d)$, where $q$ represents the current state, $s$ symbol on tape under head, $q^{\prime }$ new state, $s^{\prime }$ symbol written, $d$ direction of movement (written as $0,1$).

The full description of the machine is hence then $(n,m,l)$ where:

• $l$ is the list representing transition function
• $n$ is the number of states
• $m$ is the number of final states

The original machine can be recovered from the code. A code is a word, and as such it can be used as input for a Turing machine.

It is then possible to define a Turing machine $U$ such that, when the code of a machine $A$ is written on the tape, together with input word $w$ for $A$, $U$ decodes it and simulates the behaviour of the machine $A$ on $w$.

The machine $U$ is the universal Turing machine.