A Turing machine is a theoretical model of computation introduced by Alan Turing in 1936. It provides a precise mathematical definition of algorithm and computation.
| Component | Description |
|---|---|
| Infinite tape | One-dimensional tape divided into cells, each holding one symbol. Extends infinitely in both directions. |
| Read/write head | Positioned over one cell; can read and write a symbol. |
| State register | Holds the current state from a finite set $Q$. |
| Transition function | $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}$ — given current state and tape symbol, outputs new state, symbol to write, and direction to move. |
| Initial state | A designated start state $q_0$. |
| Halting states | $q_{\text{accept}}$ and $q_{\text{reject}}$ end computation. |
$$M = (Q,\; \Sigma,\; \Gamma,\; \delta,\; q_0,\; q_{\text{accept}},\; q_{\text{reject}})$$
Where $\Sigma$ is the input alphabet and $\Gamma \supseteq \Sigma$ is the tape alphabet (includes blank $\sqcup$).
A machine to accept inputs with an even number of 0s:
| State | Read | Write | Move | New State |
|---|---|---|---|---|
| $q_0$ (even) | 0 | 0 | R | $q_1$ |
| $q_0$ | $\sqcup$ | $\sqcup$ | — | $q_{\text{accept}}$ |
| $q_1$ (odd) | 0 | 0 | R | $q_0$ |
| $q_1$ | $\sqcup$ | $\sqcup$ | — | $q_{\text{reject}}$ |
The Turing machine model allows precise definitions of:
- Decidable problems — a TM always halts with the correct answer
- Semi-decidable problems — a TM halts on YES instances but may loop on NO
- Undecidable problems — no TM exists that always halts correctly
- Time and space complexity — measured in terms of steps and tape cells used
KEY TAKEAWAY: The Turing machine is the theoretical basis for what can and cannot be computed. It is not a physical device but a mathematical abstraction.
EXAM TIP: VCAA may ask you to describe the components of a Turing machine and explain what the transition function does. Focus on: infinite tape, read/write head, finite states, transition function, halting states.
COMMON MISTAKE: The tape is conceptually infinite — a Turing machine is a theoretical model, not constrained by physical memory. Real computers are strictly less powerful than a Turing machine.
VCAA FOCUS: Describe the general structure (tape, head, states, transition function). Give an example of a simple computation. Understand the concept of a Universal Turing Machine and why it matters.
