What is a Turing machine?
In 1936 Alan Turing imagined the simplest computer he could. It has four parts.
- Tape: a very long strip of cells. Each cell holds one symbol (for example 0, 1 or blank).
- Head: it sits on one cell. It can read the symbol and write a new one.
- State: a small note the machine keeps, like "I am going right now".
- Rule table: a list of rules of the form: in this state, reading this symbol, write that symbol, move left or right, go to that state.
The machine starts, follows the rules one by one, and stops when it reaches a halt state. Whatever is on the tape then is the answer.
Example: add 1 to a binary number
The tape holds 01011. We want 01100.
| State | Reads | Writes | Moves | Next state |
|---|---|---|---|---|
| go | 0 or 1 | same | right | go |
| go | blank | blank | left | carry |
| carry | 1 | 0 | left | carry |
| carry | 0 or blank | 1 | stay | halt |
Rule "carry, read 1, write 0" is the same as how you add by hand: 1 + 1 = 10, write 0 and carry 1 to the left.
Church–Turing thesis
People invented other models of computing too: Alonzo Church made one using functions (lambda calculus), and later came real programming languages. Every time, they turned out to be equal in power to a Turing machine.
The Church–Turing thesis says: if a problem can be solved by a clear step-by-step method (an algorithm), then a Turing machine can solve it.
It is called a thesis, not a theorem, because "clear step-by-step method" is an idea, not a maths definition, so it cannot be proved. But nobody has found a counter-example in about 90 years.
A consequence: some things are not computable by any machine. The famous one is the halting problem: no program can always tell, for every other program, whether it will finish or run forever.
Complexity analysis: counting steps
An algorithm that works is not enough. It must also be fast enough. Time complexity asks: if the input size is n, how many steps are needed? We ignore small details and keep the main growth, using Big O.
| Steps | Name | If n doubles |
|---|---|---|
| n | O(n) linear | about 2 times |
| n² | O(n²) quadratic | about 4 times |
| 2ⁿ | O(2ⁿ) exponential | squared! hopeless |
Our add-1 machine takes about 2n + 1 steps, so it is O(n). Space complexity counts the memory used, for example the number of tape cells.
Class P is the set of problems with a polynomial-time algorithm (n, n², n³ …). Whether every problem whose answer is easy to check is also easy to solve (P vs NP) is still an open question.
Try it: be the Turing machine
Take a strip of paper and draw 7 boxes. Write 0 1 1 0 1 in the middle five. Put a coin on the first digit. Use ONLY the rule table above. For each move, say the state aloud and count it. Then use the 3D: pick the number 13 and press Run. Predict the steps first, then check.
Key formulas and definitions
- Turing machine = tape + head + state + rule table
- One move: (state, symbol) → (new symbol, left/right, new state)
- Add-1 machine: about 2n + 1 steps for n bits = O(n)
- Growth order: O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ)
- Church–Turing thesis: algorithm ⇔ Turing machine computable
Worked examples
1. The tape is 0 1 0 0 1 (9). Run the add-1 machine. What is the final tape and how many steps?
The head goes right over 5 digits, one step each (5 steps), moves to the blank (1 step), then goes left: the last digit is 1, so it becomes 0 and the head moves left (1 step); the next digit is 0, so it becomes 1 and the machine halts (1 step). Final tape 0 1 0 1 0 = 10. In total 8 steps.
2. An algorithm takes 3n + 5 steps. What is its Big O?
Drop the constant 5 and the factor 3. It is O(n).
3. An algorithm takes n² steps. For n = 10 it takes 100 steps. How many for n = 30?
30² = 900 steps. n became 3 times bigger, the steps became 3² = 9 times bigger.
4. A method needs 2ⁿ steps. A computer does 10⁹ steps per second. Is n = 60 possible?
2⁶⁰ is about 1.15 × 10¹⁸ steps. Time = 1.15 × 10¹⁸ / 10⁹ = 1.15 × 10⁹ seconds, about 36 years. So n = 60 is not practical.
5. A Turing machine is in state "go" reading a blank. By the table, what does it do?
It writes a blank, moves left and goes to state "carry".
6. Can a normal laptop solve a problem that no Turing machine can solve?
No. By the Church–Turing thesis, every algorithm a laptop runs can also be run on a Turing machine. A laptop is only faster.
Common mistakes
- Thinking a Turing machine is a real machine you can buy. It is an idea used to reason about computing.
- Saying "the Church–Turing thesis is proved". It cannot be proved, because "algorithm" is an informal idea.
- Thinking a faster computer fixes a bad algorithm. A 2ⁿ method stays hopeless even on a computer 1000 times faster.
- Counting only the input size, not the steps. Complexity is how the steps grow when the input grows.