# Computing - Turing Machines

> Source: https://ollybritton.com/notes/a-level/computing/topics/turing-machines/ · Updated: 2025-02-17 · Tags: computing, regular-languages

##### What two parts does a Turing machine consist of??
* A tape that can be read and write
* A controller that determines what happens at each cell

##### How long is the tape in a Turing machine??
Infinitely long.

##### What are the three states of a cell on some tape in a Turing machine??
$1$, $0$ or blank.

##### In a Turing machine, what moves along the tape??
A read-write head.

##### What state must a Turing machine have??
A halting state.

##### In a Turing machine, what is a controller??
A finite state machine which tells the machine what to do next.

##### What are the three things a Turing machine can do in any one state??
1. Read any symbol on the tape
2. Erase or write a new symbol
3. Move the head left or right by a single space

##### In a Turing machine, what are the three parameters of a finite state machine??
Input, output, head movement.

##### Describe the 3 steps of the state transition $0,0,L$ for a Turing machine??
* A zero is inputed
* A zero is outputed
* The head moves left

##### What symbol is used to represent a state transition function??
$$
\delta
$$

##### Why is $\delta$ used as the symbol for the state transition function??
Because it means "small change".

##### What is the general pattern of a state transition function??
$$
\delta(\text{current state, input}) = (\text{next state, output, head move})
$$

##### What is a transition function??
A way to represent the transition arc between two states on a state transition diagram.

##### What does $\delta(S7, 1) = (S3, 1, R)$ mean??
If on state $S7$ and a $1$ is inputted, transition to state $S3$, write a $1$ and move the read-write head to the right.

##### ![PHOTO TRANSITION FUNCTION EXAMPLE](transition-function-example.png) For the input of $0$, what is the state transition function??
$$
\delta(S0, 0) = \delta(S0, 0, R)
$$

### 2021-01-04
##### Why is a Turing Machine useful??
Because the mathematical definition of a Turing machine defines what is computable.

##### Why is a Universal Turing Machine used??
Because otherwise a Turing machine would be needed for each operation.

##### What is the main difference between a Universal Turing Machine and a normal Turing machine??
- Turing machines have one specific purpose
- Universal Turing machines can be configured for different problems

##### What two things does a Universal Turing Machine read??
- The definition of a Turing machine
- Some input data

##### What idea did the Universal Turing Machine lead to??
The stored program computer.

##### What is a stored program computer??
A computer where the program and its data are stored in memory.

##### What kind of architecture is a stored program computer??
The von Neumann architecture.

##### Why is it not possible to create a Turing machine that solves the Halting problem??
There is no algorithm that solves the Halting problem.

##### Why is a Turing machine technically more powerful than any actual computer??
Because it has an infinite amount of memory.

### 2022-05-18
##### What is a common use of Turing machines in exam questions??
Calculating parity.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt