What is computability?
Computability asks: which problems can be solved by an algorithm at all, given unlimited time and memory? It is different from complexity, which asks how fast a solvable problem can be solved.
To answer, Alan Turing (1936) invented a very simple imaginary machine. If even this machine can do everything any computer can do, then studying it tells us the limits of all computers.
Parts of a Turing machine: tape, states, transition rules
- Tape: endless in at least one direction, split into cells. Each cell holds one symbol from a finite alphabet (for example 0, 1 and blank _).
- Read/write head: looks at one cell, can overwrite it, then moves one cell left (L) or right (R).
- Finite set of states, with one start state and one or more halting (accept) states.
- Transition function (rules): δ(current state, symbol read) = (new state, symbol to write, move).
Rules can be drawn as a state transition diagram (circles for states, arrows labelled read / write, move) or written as a table. The memory is unlimited, which is why a Turing machine is more powerful than a finite state machine.
Tracing a Turing machine
Machine "add 1 to a binary number". Head starts on the rightmost digit in state carry.
- δ(carry, 1) = (carry, 0, L): a 1 plus carry gives 0, carry moves left.
- δ(carry, 0) = (HALT, 1, –): a 0 plus carry gives 1, finished.
- δ(carry, _) = (HALT, 1, –): ran out of digits, write a new leading 1.
Trace for 1011: 1011 → 1010 → 1000 → 1100, HALT. 11 + 1 = 12 ✓. In exams you write the tape and the state after each step.
The universal Turing machine and the Church–Turing thesis
A universal Turing machine (UTM) takes, on its tape, a coded description of another Turing machine M and M's input. It then behaves exactly like M. So one fixed machine can run any program you give it as data.
This is the idea behind the stored-program (von Neumann) computer: programs and data sit together in memory, and one processor can run any program. It also explains interpreters and emulators.
Church–Turing thesis: anything that can be computed by an effective, step-by-step method can be computed by a Turing machine. It is a thesis (widely accepted), not a proof.
Non-computable problems: the halting problem
The halting problem: given any program and its input, decide whether it will eventually stop or run forever.
Turing proved no algorithm can solve this for every program. Idea of the proof: suppose a program HALTS(P, x) always answers correctly. Build TROUBLE(P): if HALTS(P, P) says "halts", loop forever; otherwise stop. Now ask what TROUBLE(TROUBLE) does: if it halts, it must loop; if it loops, it must halt. A contradiction, so HALTS cannot exist.
A yes/no problem that no algorithm can always answer is undecidable. Other examples: checking whether two programs always give the same output. This means some problems are non-computable, however fast computers get.
Decidable, tractable and intractable
- Decidable / computable: an algorithm always gives the right answer in finite time.
- Tractable: decidable and solvable in polynomial time (for example sorting).
- Intractable: decidable but only with impractical (for example exponential) time; we use heuristics.
- Undecidable: no algorithm exists at all (halting problem).
Try it: be the machine
Write 0111 on paper in boxes. Put a coin under the last digit: that is the head. Follow the three "add 1" rules, moving the coin and rewriting digits. You should end with 1000. Then design your own rule table that flips every bit (0 ↔ 1) moving right, and test it in the 3D free-play step.
Key formulas and definitions
- Turing machine = tape + read/write head + finite set of states + transition rules
- δ(state, symbol read) = (new state, symbol written, move L/R)
- Universal TM: input = description of machine M + M's input
- Church–Turing thesis: computable by an algorithm ⇔ computable by a Turing machine
- Halting problem: undecidable (no algorithm for all programs)
Worked examples
1. Trace the "add 1" machine on 0111 (head on the last digit, state carry).
011<u>1</u> → 01<u>1</u>0 → 0<u>1</u>00 → <u>0</u>000 → 1000, HALT. 7 + 1 = 8 ✓. Four steps.
2. Write rules for a machine that flips every bit, starting on the leftmost digit, and stops at the first blank.
δ(F, 0) = (F, 1, R); δ(F, 1) = (F, 0, R); δ(F, _) = (HALT, _, –). On 1011 the tape becomes 0100.
3. Why can a universal Turing machine be seen as a model of a modern computer?
Because it stores another machine's instructions on the same tape as the data and runs them: just like a computer stores a program and data in memory and the CPU executes the program.
Common mistakes
- Saying the halting problem is "too slow to solve". It is not slow; it is impossible for a general algorithm.
- Forgetting that the head moves only one cell per step and reads only one cell.
- Mixing up the order in a rule: write the new symbol, then move, then change state (all in one step).
- Thinking a Turing machine is a real machine to build. It is a mathematical model with unlimited tape.