# Turing Machines

## Theory of Computation

A Turing machine has an infinite tape (memory). There is a finite-state “program” that controls a tape head. The head can read, write and move around (in both directions) on the tape.

A typical program instructions: if the finite control is in state $p$ and the head reads $b$, then write $a$, move the head to the left and go to state $q$

# Formal Definition of TM

A Turing Machine is a 7-tuple $(Q,\Sigma, \Gamma,\delta,q_0,q_{accept},q_{reject})$

1. Q is the set of states

2. $\Sigma$ is the input alphabet not containing the special blank symbol $\sqcup$

3. $\Gamma$ is the tape alphabet satisfying $\Sigma \subset \Gamma$ and $\sqcup \in \Gamma$

4. $\delta: Q\times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$ is the transition function (If in Q moving to $\Gamma$, replace the state and move the head to the Left or Right).This is deterministic

5. $q_0\in Q$ is the start state

6. $q_{accept} \in Q$ is the accept state, and

7. $q_{reject}\in Q$ is the reject state

Important

The first $\sqcup$ denotes the start of the blanks

# Computation of TM

The tape content is unbounded but always finite; the first (leftmost) blank marks the end of the tape content

A configuration consists of three items:

1. The current state

2. The tape content

The configuration $C_1$ yields the configuration $C_2$ if the TM can legally go from $C_1$ to $C_2$ in a single step (using the transition function once)

The start configuration on an input $w\in \Sigma^*$ consists of:

• The start state $q_0$

• $w$ as the tape content

• The head location being the first (leftmost) position of the tape

An accepting or rejecting configuration is a configuration whose state is $q_{accept}$ ($q_{reject}$,respectively). Accepting and rejecting configurations are halting configurations.

A TM $\mathscr{M}$ accepts an input $w$ if there is a sequence of configurations $C_1,C_2,...,C_k$ such that

1. $C_1$ is the start configuration of $\mathscr{M}$ on input $w$

2. $C_i$ yields $C_{i+1}$ for $1\leqslant i\leqslant k-1$ (it can move from $C_1$ to $C_k$ via valid moves)

3. $C_k$ is an accepting configuration

The set of string accepted by $\mathscr{M}$ constitutes the language of $\mathscr{M}$, denoted by $L(\mathscr{M})$

# Turing-Recognisable and Turing-Decidable languages

Turing Recognisable

A language $\mathscr{L}$ is Turing-Recognisable, if there is a TM $\mathscr{M}$ that recognises it, i.e. $\mathscr{L}=L(\mathscr{M})$.

Informally it will halt for every input it accepts but will either halt or loop forever on an input it rejects
Turing Decidable