Turing Machine

A Turing machine (TM) is one of the most powerful models of computation, allowing simulation of programs and weaker models of computation. It can both read and write to its input, which it gets in the form of a tape. They are extremely important by providing a framework for general-purpose computation.

A simple Turing machine consists of:

An infinite tape divided into cells, where each cell contains a specific symbol from a finite symbol set. This could be likened to an infinite array.
A moveable head, which reads the cell at a position on the tape, and moves left or right after writing to that cell. This is similar to a pointer
A state register, which stores the current state the Turing machine is in, from a finite set of states including the halting state.
A finite set of instructions, which determine the action of the machine.

|600 %%🖋 Edit in Excalidraw, and the dark exported image%%

Definition

Turing Machine ^definition

A Turing Machine, $M$ is defined as the 8-tuple:
$M = (Σ, Γ, b, Q, δ, q_{0}, q_{a}, q_{r})$

$Σ$ = The input symbol alphabet

$Γ$ = The tape alphabet, which is the input symbol alphabet, plus any addition symbols we want to write to the tape. Hence $Σ \subseteq Γ$

$b \in Γ$ = The blank symbol, (usually $\textvisiblespace$ ), which appears infinitely many times in the tape after the input string. Note that $b \in / Σ$ .

$Q$ = The finite set of all states

The state transition function, $δ$ , which allows transitioning from one state to another and can optionally overwrite the current tape character and moves the tape left or right$$ \delta: Q \setminus { q_{a}, q_{r} }\times \Gamma \to Q \times \Gamma \times { \text{L, R} } \quad\quad \delta(q_{cur},w_{cur}) = (q_{next}, w_{overrwrite}, \text{L or R})

$* $q_{0}$ = The initial state * $q_{a}$ = The (halting) *accept state*. Note: $q_{a}$ is sometimes written as a set, but this is equivalent, since a transition to any accepting state $\neq q_{a}$ can just point to $q_{a}$, resulting in one accept state. * $q_{r}$ = The (halting) reject state. Note: Similar to $q_{a}$, $q_{r}$ could be modelled as an equivalent set. Unlike other [machine models](Computational%20Model.md), a Turing Machine can do *three* possible things when given an input string $w$: * It can **halt**: * And Accept $w$ (if it ends up in $q_{a}$) * Or Reject (if it is in $q_{r}$) * Or it can **run forever**, trapped in an infinite loop!$

There are many, many formalisations of a Turing Machine

Some don’t have the $b$ definition, some use $F$ instead of $q_{a}$ . Use the definition above, don’t use the definition above. Noodles, don’t noodles. Your choice.

Decider ^def-decider

A Turing Machine $M$ is a decider if $M$ halts on all inputs (it never loops forever)

Acceptance

TM Acceptance (String) ^def-string-acceptance

Let $M$ be a Turing Machine, having various configurations $C_{1}, C_{2}, \dots C_{n}$ when given an input formula $w$ . Then:
$M accepts w$ $⟺$ $C_{1} ⟹ C_{2} ⟹ \dots ⟹ C_{k} where C_{1} = q_{0} w and C_{k} is in the accept state(s)$

Notation

In a state diagram, the transition function is notated as:

δ (q_{0}, a) = (q_{1}, b, R)

%%🖋 Edit in Excalidraw, and the dark exported image%%

If the TM doesn’t overwrite the input character, we can shorten it to:

a \to R

(which means when it encounters an $a$ , don’t overwrite it and move the tape right)

Decidability & Recognisability

|400 %%🖋 Edit in Excalidraw, and the dark exported image%%

See Recognisability and Decidability!

TM Configurations

A Turing Machine configuration is, essentially, a ‘snapshot’ of the current state of the TM. It captures:

The current state $q$
The contents of the input tape
The location of the tape head

It is notated as:

ab q abb

corresponding to: %%🖋 Edit in Excalidraw, and the dark exported image%%

Note that the current head is to the left of where the state $q$ is placed in the TM configuration.

We can apply the transition function $δ$ over configurations (since they capture the input tape/string aswell). Applying $δ$ to a configuration $C$ produces a new configuration $C^{'}$ . This is notated as:

C ⟹ C^{'}

For example:

$u q bv ⟹ uc q v ⟺ δ (q, b) = (t, c, R)$
$u q bv ⟹ t ucv ⟺ δ (q, b) = (t, c, L)$
$q buv ⟹ t cuv ⟺ δ (q, b) = (t, c, L)$ (Head cannot move left past first tape alphabet.)

The starting configuration of a TM $M$ for an input string $w$ is always $q_{0} w$

Turing Machines Are More Powerful Than PDAs

Just like there are certain non-regular languages, which cannot be recognised by finite state automata, there are also certain languages which are not context-free and so cannot be recognised by pushdown automata. One such example is the language:

L = {0^{n} 1^{n} 2^{n} ∣ n \in N_{0}}

This language can however, be recognised by a Turing Machine. The pseudocode for such a machine is given below:

TM M:
	# Preprocessing input
	Move head Right Until Non-Blank Character
	Check if tape is of form 0*1*2* (possible in FSA)
	
	While possible:
		Return head to start
		Move head Right
		Replace one instance of 'a','b' and 'c' with x
		If any symbol is missing, Reject
		
	If crossed out the last symbol of 'a','b' and 'c', Accept

TM Simulation

Theorems

T1: Determinism Equivalence

Every non-deterministic Turing Machine (NTM) has an equivalent deterministic Turing Machine (DTM). That is, non-deterministic Turing Machines are no more powerful then regular Turing Machines. #TODO proof

Examples

A Simple Turing Machine

Give the specifications for a Turing Machine that recognises the language:
$L = {w ∣ w has a substring 11} Σ = {0, 1}$

Solution

Let $M = (Σ, Γ, Q, δ, q_{0}, F, \textvisiblespace)$ :

$Σ = {0, 1}$

$Γ = {0, 1} = Σ$

$Q = {A, B, C}$

$q_{0} = A$

$F = {C}$

The state diagram below describes $δ$ and $M$ : %%🖋 Edit in Excalidraw, and the dark exported image%%

Questionably Accurate Notes

Explorer