The Limits of Computing

Grade 9 counted an algorithm’s steps as its data grew, and gave the six kinds of growth their names in big O notation Grade 9: How the work grows. Grade 11 and Unit 1 have used it ever since: a heap adds and takes in O(log n), Dijkstra’s algorithm with a heap is fast, trying every route through n villages is hopeless. Here is the whole family again, slowest-growing first, with what happens to the work when the data becomes ten times bigger:

(Why 3.3? Because 2³·³ ≈ 10: ten times the data is about 3.3 more halvings.) Unit 1’s trek, trying every order of the villages, grows even faster than 2ⁿ: its work is O(n!).

Reading big O from a program

You rarely need to count every step. Look at the loops and the calls:

• A fixed number of steps, whatever the size of the data: O(1).
• One loop that goes through the n items: O(n).
• A loop inside a loop, each going through the items: **O(n²)**. Three deep: O(n³).
• A loop that halves what is left each time round: O(log n).
• n times something that is O(log n), like pushing n items onto a heap: O(n log n).
• A function that, for each item, tries the rest both with it and without it (two calls each time): O(2ⁿ).

Then keep only the part that grows fastest, and drop the numbers in front of it. A program that does 3n² + 5n + 2 steps is O(n²): for a million items, 3n² is three million million while 5n is five million, too small to matter. Big O tells you how the work grows, not how long one run takes.

Will it finish in time?

Big O lets you predict, before you wait. Measure the program once on data you have, then scale.

Space as well as time

A program uses memory as well as time, and memory can run out too: a phone with 4 GB of memory can’t hold a table of 10 GB. The space complexity of an algorithm is how the extra memory it needs grows with its data, written in big O like time. (The data itself isn’t counted: every program needs that much.)

The last two rows show the trade you meet everywhere. Unit 1’s memoization spent memory to save time: remembering every answer made a slow program fast. And the edit distance table can be cut down: each row is worked out only from the row above it, so a program that keeps just two rows uses far less memory for the same answer (if it only needs the distance, not the list of edits).

There is one kind of memory that is easy to forget: the call stack. Every recursive call that is still waiting keeps its own variables on the stack, as Grade 11 showed Grade 11: When recursion goes wrong. So a function that calls itself n deep uses O(n) memory even if it stores nothing else. Here is a short recursive total:

def total(marks):    if len(marks) == 0:        return 0    return marks[0] + total(marks[1:]) print(total(list(range(1, 101))))print(total(list(range(1, 5001))))

Traceback (most recent call last):  File "main.py", line 7, in <module>    print(total(list(range(1, 5001))))          ~~~~~^^^^^^^^^^^^^^^^^^^^^^  File "main.py", line 4, in total    return marks[0] + total(marks[1:])                      ~~~~~^^^^^^^^^^^  File "main.py", line 4, in total    return marks[0] + total(marks[1:])                      ~~~~~^^^^^^^^^^^  File "main.py", line 4, in total    return marks[0] + total(marks[1:])                      ~~~~~^^^^^^^^^^^  [Previous line repeated 994 more times]RecursionError: maximum recursion depth exceeded

It adds 1 to 100 (5050) without trouble, then fails on 5,000 numbers: Python allows about 1,000 calls waiting at once. And it is worse than it looks. marks[1:] makes a new list, a copy of all but the first mark, and each waiting call holds on to its own copy: n − 1 marks, n − 2, n − 3, … all at once. That adds up to about n²/2 numbers: O(n²) space, and O(n²) time to copy them. A plain loop with one running total does the same job in O(n) time and O(1) space.

The algorithms so far are deterministic: given the same input, they take exactly the same steps and give exactly the same answer, every time. Grade 9 met algorithms that make random choices on purpose Grade 9: Algorithms that use chance, and such a probabilistic (or randomized) algorithm can be the best tool there is. They come in two kinds:

• Always right, but the time varies. Picking the pivot of a quicksort at random gives the right sorted list every time; only the time depends on luck, and bad luck is almost impossible on a big list.
• Always fast, but right only with a very high chance. This kind can be wrong. Its use is that the chance of a wrong answer can be made as small as you like, by running it more times.

The second kind protects your money every day. When you open a banking app, your phone and the bank agree on secret keys, and some kinds of key (Unit 7’s RSA) are built from two huge prime numbers, each hundreds of digits long. How does a computer know that a 300-digit number is prime? The school method, trying every divisor up to its square root, would need more divisions than there are atoms in the Earth.

The Miller–Rabin test asks a different question. It picks a random number a and does a short calculation with a and n. If n is prime, the calculation always comes out a certain way. If n isn’t prime, it comes out that way for at most a quarter of the possible a’s; for the rest, a is a witness: proof that n is not prime. So each round that finds no witness cuts the chance of being fooled to a quarter or less. After 20 rounds the chance is at most 1 in 4²⁰, less than one in a million million.

import math, random def is_prime_slow(n):    """Try every divisor up to the square root: always right, but slow."""    if n < 2:        return False    d = 2    while d * d <= n:        if n % d == 0:            return False        d = d + 1    return True def probably_prime(n, rounds=20):    """Miller-Rabin. A prime always passes. A number that isn't prime    passes one round, by bad luck, with a chance of at most 1 in 4."""    if n < 4:        return n == 2 or n == 3    if n % 2 == 0:        return False    d, s = n - 1, 0    while d % 2 == 0:                # write n - 1 as d × 2^s, d odd        d, s = d // 2, s + 1    for _ in range(rounds):        a = random.randrange(2, n - 1)        x = pow(a, d, n)             # a^d, keeping the remainder after ÷ n        if x == 1 or x == n - 1:            continue                 # no witness this round        witness = True        for _ in range(s - 1):            x = pow(x, 2, n)            if x == n - 1:                witness = False                break        if witness:            return False             # a proves that n is not prime    return True random.seed(7)for n in [97, 561, 1_000_000_007]:    print(n, is_prime_slow(n), probably_prime(n)) big = 2**61 - 1print(big, probably_prime(big))print(f"Dividing would try about {math.isqrt(big):,} divisors")print(big * 1_000_000_007, probably_prime(big * 1_000_000_007))

97 True True561 False False1000000007 True True2305843009213693951 TrueDividing would try about 1,518,500,249 divisors2305843025354595015495857657 False

pow(a, d, n) works out a to the power d and keeps only the remainder after dividing by n, without ever making the huge number itself, so each round takes only a few hundred multiplications even for a 300-digit n. The number 561 is a famous trap: 561 = 3 × 11 × 17, yet it fools simpler tests that check only aⁿ⁻¹ (it is a Carmichael number). Miller–Rabin isn’t fooled. The last number is two primes multiplied together; the test finds a witness at once, though it doesn’t say what the two primes are.

Evaluating an algorithm means asking three things, with test cases or measurements, not opinions:

Is there a fast test with no chance at all? Grade 9 told the answer Grade 9: Prime or not?: in 2002 Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena, at IIT Kanpur, found one. It is slower in practice, so programs that make keys still use Miller–Rabin.

A ticket gate at a stadium or a museum has a turning arm. Scan a ticket and the arm unlocks; push through and it locks again behind you. Push without a ticket and it doesn’t move. What does the gate need to remember to do this right? Not how many tickets were scanned this morning, not who came through last. Only one thing: is it locked or unlocked now?

Each thing a machine can be remembering is called a state. The gate has two states, Locked and Unlocked. Things that happen to it are inputs (a ticket, a push), and an input moves it from one state to another: a transition. A machine with a fixed number of states, which moves between them on its inputs, is a finite state machine (FSM). One state is the start state, where it begins.

An FSM can be written down in two ways that say exactly the same thing:

• a state diagram: a circle for each state, an arrow for each transition, labeled with its input; an arrow from nowhere marks the start;
• a transition table: a row for each state, a column for each input, and in each cell the state it moves to.

Two tickets in a row show a weakness: the second ticket is wasted, because the gate can’t remember “two people may come through”. To remember that, it would need more states (Unlocked for one, Unlocked for two…). Whatever an FSM needs to remember must be one of its states: it has no other memory.

A machine that gives tea

A tea machine in a hospital corridor sells a cup for Rs 30 and takes Rs 10 and Rs 20 notes. Its states are the money it holds so far: Rs 0, Rs 10 or Rs 20. Some transitions do something as well as change the state: give out a cup, give change, give money back.

FSMs are everywhere: a lift, traffic lights, a washing machine’s cycle, a phone’s lock screen, the enemy in a game (wandering, chasing, running away). Engineers draw the diagram first because it shows at once a case nobody thought of: a state with no arrow for some input is a question nobody has answered yet.

An FSM in Python

The transition table becomes a dictionary: each key is a (state, input) pair, and its value the next state. The whole machine is then three lines in a loop.

gate = {    ("Locked", "ticket"): "Unlocked",    ("Locked", "push"): "Locked",    ("Unlocked", "ticket"): "Unlocked",    ("Unlocked", "push"): "Locked",} state = "Locked"through = 0for event in ["push", "ticket", "push", "push", "ticket", "ticket", "push"]:    new = gate[(state, event)]    if state == "Unlocked" and event == "push":        through = through + 1    print(f"{state:8} + {event:6} → {new}")    state = new print("People through:", through)

Locked   + push   → LockedLocked   + ticket → UnlockedUnlocked + push   → LockedLocked   + push   → LockedLocked   + ticket → UnlockedUnlocked + ticket → UnlockedUnlocked + push   → LockedPeople through: 2

Seven inputs, two tickets used, two people through, one ticket wasted. The machine’s rules are data, a table, not if statements: to change the gate, you change the table and the loop stays the same. ({state:8} pads the state to 8 characters, so the columns line up.)

In Grade 11 you wrote regular expressions to find amounts and phone numbers in text Grade 11: Patterns in text. Here is a pattern for an amount in rupees, with or without paisa: \d+(\.\d\d)?, one or more digits, then perhaps a dot and two more digits. It matches 250 and 12.50 but not 12.5 or .50.

Now read the text one character at a time, and ask what you must remember as you go. At the start, you have seen nothing. After some digits, you have a whole amount so far. After the dot, you need a digit; after that, one more. That is a list of states, and the pattern is a machine:

A machine like this, which reads a text and ends by accepting or rejecting it, is an FSM whose inputs are characters, and its double circles are its accepting states. This is not a trick that works for one pattern. In 1951 the American mathematician Stephen Kleene proved (in a report published in full in 1956) that every regular expression can be turned into a finite state machine, and every finite state machine into a regular expression: they describe exactly the same patterns.

Here is the machine as a Python dictionary, tested against Python’s own re on the same texts:

import re NEXT = {    "S": {"digit": "A"},    "A": {"digit": "A", "dot": "B"},    "B": {"digit": "C"},    "C": {"digit": "D"},    "D": {},}ACCEPT = {"A", "D"} def kind(ch):    if ch.isdecimal():        return "digit"    if ch == ".":        return "dot"    return "other" def machine_accepts(text):    state = "S"    for ch in text:        state = NEXT[state].get(kind(ch))        if state is None:            return False                # no arrow: rejected    return state in ACCEPT for t in ["250", "12.50", "12.5", ".50", "1,200", "7.", "0.05", "१२५", ""]:    m = machine_accepts(t)    r = re.fullmatch(r"\d+(\.\d\d)?", t) is not None    print(f"{t!r:9} machine: {m!s:5}  regex: {r!s:5}  {'agree' if m == r else 'DIFFERENT'}")

'250'     machine: True   regex: True   agree'12.50'   machine: True   regex: True   agree'12.5'    machine: False  regex: False  agree'.50'     machine: False  regex: False  agree'1,200'   machine: False  regex: False  agree'7.'      machine: False  regex: False  agree'0.05'    machine: True   regex: True   agree'१२५'     machine: True   regex: True   agree''        machine: False  regex: False  agree

NEXT[state].get(kind(ch)) gives the next state, or None when there is no arrow. ch.isdecimal() is true for exactly the characters Python’s \d matches, Nepali digits included.

Grade 11 told where the idea came from Grade 11: From nerve cells to grep: Kleene was studying what networks of model nerve cells could recognize. And when Ken Thompson built regular expressions into a text editor in 1968, his program did exactly what this section does: it turned the pattern into a machine, then ran the machine along the text.

Here is a job that sounds just as easy: check that the brackets in a sum balance, like (2 + 3) × ((4 − 1) + 5). Grade 11 did it in a few lines with a stack Grade 11: Brackets that match. Can an FSM do it, and so a regular expression?

Try to build one. It must remember how many brackets are open: a state for 0 open, one for 1 open, one for 2, one for 3. Here it is, for any text with brackets up to three deep:

Add a state 4, and five deep beats it. Add a hundred states, and a hundred and one deep beats it. Whatever machine you build, someone can write brackets deeper than it has states, and here is why it must then go wrong. Say the machine has 10 states. Feed it (, ((, (((, … up to 11 brackets. Eleven texts and only ten states, so two of them, say 4 brackets and 7, leave the machine in the same state. From then on it can’t tell them apart: whatever follows, it does the same with both. Follow each with )))). After 4 brackets that balances, and must be accepted; after 7 it doesn’t, and must be rejected. The machine gives the same answer to both, so one answer is wrong.

So no finite state machine, and no regular expression, can check that brackets of any depth balance. It isn’t that nobody has been clever enough: it can’t be done. The job needs memory that can grow as deep as the brackets do, like a stack.

Grammars: rules that can use themselves

To describe brackets, we need rules that can contain themselves: “an expression in brackets is an expression”. A set of rules like that is a grammar, and computer scientists write it in BNF (Backus–Naur form). Start with something a regular expression can do too, a Nepali mobile number:

<mobile>  ::= <number> | +977<number> | +977-<number><number>  ::= 9 <network> <digit> <digit> <digit> <digit> <digit> <digit> <digit> <digit><network> ::= 6 | 7 | 8<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

How to read it:

• Each line is a rule. The name on the left of ::= (“is defined as”) is made of what is on its right.
• A name in angle brackets, like <digit>, is a non-terminal: it stands for something defined by another rule.
• Anything else, like 9 or +977, is a terminal: written exactly as it appears in the text.
• | means or: one of the choices.
• Things written one after another come one after another.

So a mobile number is a number, perhaps with +977 or +977- in front, and a number is a 9, then 6, 7 or 8, then eight digits. To check a text against a grammar, find a way to build it from the first rule. For +9779841234567: it starts +977, so it is the second choice of <mobile>, and the rest, 9841234567, must be a <number>: 9, then 8 (a <network>), then eight <digit>s. It fits.

The same rules can be drawn as syntax diagrams: follow the lines from the left to the right; every way through spells a text the grammar allows.

A grammar for arithmetic

Now the grammar a regular expression can’t match: sums like 2 × (7 − 3) + 10 ÷ 5.

<expression> ::= <term> | <expression> + <term> | <expression> − <term><term>       ::= <factor> | <term> × <factor> | <term> ÷ <factor><factor>     ::= <number> | ( <expression> )<number>     ::= <digit> | <digit> <number>

(<digit> is as before.) Look at three things in it:

• A rule that uses itself. <number> ::= <digit> | <digit> <number> says a number is a digit, or a digit followed by a number: so one digit, two, three, as many as you like. That is how BNF says “one or more” without a +.
• Brackets. A <factor> can be ( <expression> ), and that expression can contain factors in brackets, which contain expressions… to any depth. This rule, a grammar using itself inside a pair of brackets, is exactly what no machine with fixed states can follow.
• Which goes first. Multiplication is in <term>, deeper than addition in <expression>. So in 2 + 3 × 4, the 3 × 4 must be built first, as one term, before it is added: the grammar itself says × goes before +, without a separate rule. And <expression> − <term> builds 8 − 3 − 2 from the left, as (8 − 3) − 2 = 3, never 8 − (3 − 2) = 7.

Checking a text against a grammar in Python

Each rule becomes a function that reads its part of the text and moves along it; a non-terminal in a rule becomes a call to that rule’s function. This kind of checker is called a recursive descent parser, and many real compilers are built this way. The program uses Python’s * and / for × and ÷.

class Parser:    """Checks a text against the grammar for arithmetic, one method per rule."""     def __init__(self, text):        self.s = text.replace(" ", "")        self.i = 0                                  # how far it has read     def next(self):        return self.s[self.i] if self.i < len(self.s) else "the end"     def fail(self, wanted):        raise ValueError(f"wanted {wanted} at character {self.i + 1}, found {self.next()}")     # <expression> ::= <term> | <expression> + <term> | <expression> − <term>    def expression(self):        self.term()        while self.next() in ("+", "-"):            self.i += 1            self.term()     # <term> ::= <factor> | <term> × <factor> | <term> ÷ <factor>    def term(self):        self.factor()        while self.next() in ("*", "/"):            self.i += 1            self.factor()     # <factor> ::= <number> | ( <expression> )    def factor(self):        if self.next() == "(":            self.i += 1            self.expression()            if self.next() != ")":                self.fail(")")            self.i += 1        elif self.next().isdigit():            while self.next().isdigit():            # <number>: one or more digits                self.i += 1        else:            self.fail("a number or (") def check(text):    p = Parser(text)    try:        p.expression()        if p.i < len(p.s):            p.fail("an operator or the end")        return "follows the grammar"    except ValueError as e:        return str(e) for t in ["2+3*4", "(2+3)*4", "2*(7-3)+10/5", "((7))", "2*(3+4", "2+*3", "4(5)", "(((((((((1)))))))))"]:    print(f"{t:22} {check(t)}")

2+3*4                  follows the grammar(2+3)*4                follows the grammar2*(7-3)+10/5           follows the grammar((7))                  follows the grammar2*(3+4                 wanted ) at character 7, found the end2+*3                   wanted a number or ( at character 3, found *4(5)                   wanted an operator or the end at character 2, found ((((((((((1)))))))))    follows the grammar

The rule <expression> ::= <expression> + <term> can’t become a function that first calls itself: it would call itself again before reading anything, for ever, until Python’s stack ran out. So the program does what the syntax diagram does: a term, then a loop for each + or − and the next term. Nine brackets deep is no problem: each ( is a call to expression that waits on Python’s call stack until its ) comes. The stack that no FSM has is right there, in the calls.

Type 3 + 4 × 2 into a simple calculator, pressing each key in turn. Many simple calculators show 14: they work out 3 + 4 = 7 as soon as you press ×, then 7 × 2. A scientific calculator, or a phone’s, shows 11, because it knows × comes before +. To do that, it must hold the 3 and the + while it reads ahead, and with brackets it may have to hold many things at once. How does a machine keep track?

Operators after their numbers

In 1924 the Polish logician Jan Łukasiewicz showed that formulas can be written with no brackets at all, if every operator is written before its two operands: + 3 × 4 2. Turned the other way round, with every operator after its two operands, it is called Reverse Polish notation (RPN), or postfix (ordinary 3 + 4 is infix: the operator is in between):

RPN needs no brackets and no rule about × before +: the order of the symbols says everything. And it is easy for a machine, with a stack:

1. Read the symbols from left to right.
2. A number: push it onto the stack.
3. An operator: pop the top two numbers (the first popped is the right-hand one), work out the answer, and push it.
4. At the end, the one number on the stack is the answer.

def rpn(text):    stack = []    for token in text.split():        if token in ("+", "-", "*", "/"):            right = stack.pop()             # the top is the right-hand number            left = stack.pop()            if token == "+":                stack.append(left + right)            elif token == "-":                stack.append(left - right)            elif token == "*":                stack.append(left * right)            else:                stack.append(left / right)        else:            stack.append(float(token))    if len(stack) != 1:        raise ValueError(f"{len(stack)} numbers left: an operator is missing")    return stack[0] for e in ["3 4 2 * +", "3 4 + 2 *", "8 3 - 2 -", "5 1 2 + 4 * + 3 -", "10 4 /"]:    print(f"{e:20} = {rpn(e)}")

3 4 2 * +            = 11.03 4 + 2 *            = 14.08 3 - 2 -            = 3.05 1 2 + 4 * + 3 -    = 14.010 4 /               = 2.5

Every number is pushed once and every operator pops twice and pushes once, so working out an RPN expression is O(n) in its length. Grade 11 showed that Python itself runs your program on a stack machine: BINARY_OP takes the top two values off a stack and puts back the answer Grade 11: Reading Python’s bytecode. Python’s bytecode for t + 10 is, in effect, the RPN t 10 +.

From ordinary to RPN: the shunting-yard algorithm

People write infix. So a calculator or a compiler must turn infix into RPN first. In 1961 Edsger Dijkstra, whose shortest-route algorithm you used in Unit 1, gave a method with a stack for the operators. He named it after a railway shunting yard, where wagons are moved onto a side track to wait and then put back into the train in a new order. Read the expression from the left:

1. A number goes straight to the output.
2. An operator first moves to the output every operator on top of the stack that binds at least as tightly (× and ÷ bind more tightly than + and −; two of the same level count as “at least as tightly”, which works them out from the left), stopping at a (. Then it goes onto the stack itself, to wait for its right-hand number.
3. A ( goes onto the stack.
4. A ) moves operators from the stack to the output until it reaches the (; then both brackets are thrown away.
5. At the end, every operator left on the stack moves to the output, top first.

import re BINDS = {"+": 1, "-": 1, "*": 2, "/": 2} def to_rpn(text):    output, ops = [], []    for token in re.findall(r"\d+|[-+*/()]", text):        if token in BINDS:            while ops and ops[-1] != "(" and BINDS[ops[-1]] >= BINDS[token]:                output.append(ops.pop())            ops.append(token)        elif token == "(":            ops.append(token)        elif token == ")":            while ops[-1] != "(":                output.append(ops.pop())            ops.pop()                         # throw the ( away        else:            output.append(token)              # a number    while ops:        output.append(ops.pop())    return " ".join(output) for e in ["3 + 4 * 2", "(3 + 4) * 2", "8 - 3 - 2", "2 * (7 - 3) + 10 / 5"]:    print(f"{e:22} → {to_rpn(e)}")

3 + 4 * 2              → 3 4 2 * +(3 + 4) * 2            → 3 4 + 2 *8 - 3 - 2              → 8 3 - 2 -2 * (7 - 3) + 10 / 5   → 2 7 3 - * 10 5 / +

Look at the first line of the loop: re.findall(r"\d+|[-+*/()]", text) splits the text into tokens with a regular expression, which is a machine. Then the stack does what no machine can: brackets of any depth. That is how a compiler is built, as Grade 11 described Grade 11: What a compiler does: a machine reads the words (lexical analysis), and a stack, or the call stack of a recursive descent parser, finds the structure (parsing).

In 1936 the word “computer” meant a person: someone, very often a woman, paid to do long calculations with pencil and paper. That year Alan Turing, a 23-year-old mathematician at Cambridge University in England (you met him in Grades 6 and 10, asking whether machines can think), asked a question nobody had asked so plainly: what exactly does such a person do? They look at a few symbols on the paper, write some, look somewhere else, and keep in their head where they are in the method. Turing took each part to its simplest:

• The paper becomes a tape: a row of squares, as long as needed in both directions, each square blank or holding one symbol.
• The eyes and pencil become a head, over one square at a time, which can read its symbol, write a new one, and move one square left or right.
• What the person keeps in mind becomes a state, one of a fixed list, as in an FSM.
• The method becomes rules, each of the form: in this state, reading this symbol: write this symbol, move left or right (or stay), and go to this state.

The machine starts in its first state with its head on the first symbol, and follows the rule that fits, step after step. When it reaches a halting state, it stops, and what is on the tape is the answer. This is a Turing machine. It is an FSM with one difference: the tape, a memory that never runs out.

Now the job no FSM can do. This machine checks that brackets of any depth balance, by crossing them off in pairs: it walks right to the first ), crosses it out with an x, walks back to the nearest ( and crosses that out too, and starts again. When no ) is left, there must be no ( left either.

A machine for everything

A Turing machine looks too simple to matter: one square at a time, a few rules. But in the same paper Turing showed something remarkable. Its rules can be written on its tape as symbols, so one machine, a universal Turing machine, can read another machine’s rules from its tape and do whatever that machine would do. One machine, any program, given as data: that is the idea of every computer you have ever used, which keeps its programs in the same memory as its data (Grade 11’s Von Neumann machine).

Everything every computer can do, a Turing machine can do too: memory becomes squares of the tape, a register a stretch of squares, each instruction of a processor a group of rules. It would be hopelessly slow, but speed isn’t the question; whether it can be done at all is. The other way round is easy to see: here is a Turing machine run by a Python program.

def run(rules, text, state, halt, limit=10_000):    tape = dict(enumerate(text))           # square number → symbol    head = 0    steps = 0    while state not in halt:        if steps == limit:            return None                     # it may never stop: give up        symbol = tape.get(head, "_")        # a square never written is blank        write, move, state = rules[(state, symbol)]        tape[head] = write        head = head + {"L": -1, "R": 1, "S": 0}[move]        steps = steps + 1    squares = sorted(i for i in tape if tape[i] != "_")    return "".join(tape[i] for i in range(squares[0], squares[-1] + 1)), steps add_one = {    ("right", "0"): ("0", "R", "right"),    ("right", "1"): ("1", "R", "right"),    ("right", "_"): ("_", "L", "carry"),    ("carry", "1"): ("0", "L", "carry"),    ("carry", "0"): ("1", "S", "done"),    ("carry", "_"): ("1", "S", "done"),} for n in ["1011", "111", "0"]:    print(n, "→", run(add_one, n, "right", {"done"}))

1011 → ('1100', 8)111 → ('1000', 8)0 → ('1', 3)

So Python can do anything a Turing machine can, and a Turing machine anything Python can. Every programming language with variables, loops (or recursion) and a memory that can grow can do the same as a Turing machine: such a language is called Turing complete. Python is; so are the block programs of Grade 6, given enough memory. A spreadsheet’s formulas, with no way to loop, are not, unless the spreadsheet adds one.

In 1936 the American logician Alonzo Church reached the same limits by a completely different route, a notation of functions (the lambda calculus, the grandfather of Python’s lambda), and the two descriptions turned out to compute exactly the same things. Every other description anyone has proposed since has too. This gives the Church–Turing thesis: anything that can be computed by following a method step by step can be computed by a Turing machine. It is called a thesis, not a theorem, because “a method” isn’t a mathematical object that can be proved about; but nobody has ever found a method that a Turing machine can’t follow.

Here is a short program. Start with any whole number. If it is even, halve it; if it is odd, multiply it by 3 and add 1. Stop when you reach 1.

def steps_to_one(n):    steps = 0    while n != 1:        if n % 2 == 0:            n = n // 2        else:            n = 3 * n + 1        steps = steps + 1    return steps for n in [6, 7, 27, 97, 871]:    print(n, steps_to_one(n))

6 87 1627 11197 118871 178

From 27 it climbs as high as 9,232 before it falls back to 1, after 111 steps. Does it stop for every starting number? Nobody knows. This is the Collatz problem, posed by Lothar Collatz in 1937. Computers have checked every number up to 2⁷¹ (as of 2025), about 2,400 million million million, and every one reaches 1, but nobody has proved that no number goes on for ever.

So: does this program stop? It looks like a question a clever enough program could answer. Imagine it: a function halts(program, input) that reads any program and its input, always finishes, and answers True if the program would stop and False if it would run for ever. Phone makers would build it in; teachers would run it on every homework program. This is the halting problem: is there such a function?

Why there can’t be

Turing proved in 1936 that there isn’t, with an argument short enough to follow here. Suppose someone gives you halts. Use it to write this program:

def contrary(program):    if halts(program, program):    # would this program stop, given itself as its input?        while True:                # then don’t stop: loop for ever            pass    else:        return                     # it wouldn’t stop: so stop at once

A program is only text, so a program can be given to a program as its input (a compiler reads programs all day). Now give contrary itself: contrary(contrary). Does it stop?

• If halts says True, “contrary stops when given itself”: then contrary, following its own first branch, loops for ever. So it doesn’t stop, and halts was wrong.
• If halts says False, “contrary runs for ever when given itself”: then contrary takes its second branch and stops at once. So it stops, and halts was wrong again.

Either way, halts gave the wrong answer about one program. And contrary was written from halts in five lines, so whatever halts anyone ever writes, its own contrary beats it. No program can decide, for every program and every input, whether it stops. The halting problem is undecidable.

It isn’t about computers being too slow, or programmers too weak: like the brackets and the FSM, it is impossible, proved. It follows that many other checkers can’t be perfect either. A perfect virus checker would have to say, for every program, whether it ever does something harmful; ask it about a program that does harm only after some other program halts, and it would be solving the halting problem. In 1953 Henry Rice proved the general rule: no program can decide, for every program, any question about what it does when it runs (except questions that are true of every program or of none).

Back to Unit 1’s health worker and her trek through 20 villages Grade 12: A trek through 20 villages. Trying every round trip would take years; nobody knows a method that always finds the shortest one quickly. Ask a slightly different question: is there a round trip shorter than 90 km? Now suppose a friend says, “Yes, this one”, and hands you a route. Checking it is easy: is every village in it exactly once, and does it come back to base? Add up its 20 legs: is the total under 90 km?

import math def check_trek(trek, spots, limit):    """True if trek visits every village once, returns to base, and is under limit km."""    if trek[0] != 0 or trek[-1] != 0 or sorted(trek[:-1]) != list(range(len(spots))):        return False    km = 0    for i in range(len(trek) - 1):        km = km + math.dist(spots[trek[i]], spots[trek[i + 1]])    print(f"{len(trek) - 1} legs added: {km:.1f} km")    return km < limit # Unit 1's map of 20 villages (km east and north of the base, village 0)spots = [(0, 0), (11, -5), (-4, -6), (-2, 9), (-7, -9), (1, 4), (-10, -6), (-8, 1), (3, 9), (-6, -3),         (-2, 4), (-10, 7), (-10, -3), (6, -2), (10, 0), (-3, -1), (-7, -6), (-5, 9), (-12, 0), (7, 5)]in_order = [0] + list(range(1, 20)) + [0]from_friend = [0, 15, 9, 2, 16, 4, 6, 12, 18, 7, 11, 17, 3, 10, 5, 8, 19, 14, 1, 13, 0]print(check_trek(in_order, spots, 90))print(check_trek(from_friend, spots, 90))

20 legs added: 248.3 kmFalse20 legs added: 88.2 kmTrue

Checking takes 20 additions, however the route was found: O(n) work. The friend’s trek is the one that Unit 1’s Plan the trek found by nearest next and uncrossing, and it passes. Finding such a route may take far more work, and nobody knows a method that is always fast. Now ask for a trek under 85 km. On this map the best is 88.2 km, so the answer is no, and there is nothing a friend can hand you to check: Unit 1 knew it only because a slow exact program, run for that unit, worked it out. The gap between checking an answer and finding one is the heart of the most famous open question in computing.

P and NP

First, what does “fast” mean? Computer scientists call an algorithm fast, efficient, when its work grows at most like a power of the size of the problem: n, n², n³, even n¹⁰. That is called polynomial time. Work that grows like 2ⁿ or n! is not: for big problems it is hopeless on any computer. Then:

• P is the set of yes-or-no problems that can be solved in polynomial time. Is there a route from Kathmandu to Tansen under 310 km? (Dijkstra’s algorithm.) Is this list sorted? Is this number prime? (Since 2002, in a deterministic way.)
• NP is the set of yes-or-no problems where, whenever the answer is yes, there is a proposed answer that can be checked in polynomial time. Is there a round trip under 90 km? (Check the route you are given.) Can this sudoku be completed? (Check the filled grid.) Is this big number the product of two smaller ones? (Multiply the two you are given.)

Every problem in P is in NP: if you can solve it fast, you can check it fast (just solve it). The question is the other way round:

P versus NP: if an answer can be checked quickly, can it always be found quickly?

Most computer scientists expect the answer is no, that some problems in NP are truly harder to solve than to check. Nobody has proved it either way.

The hardest problems in NP

In 1971 Stephen Cook, an American working at the University of Toronto in Canada, proved something astonishing. There is a problem in NP (whether a logic formula of ANDs, ORs and NOTs, Grade 11’s Boolean algebra, can be made true by some choice of its variables) with this property: every problem in NP can be turned into it quickly. So a fast method for that one problem would give a fast method for all of NP. A problem with that property is called NP-complete. In 1972 Richard Karp showed that 21 well-known problems are NP-complete, and since then thousands more have been found: the trek’s yes-or-no question, packing a bag with the most useful things (the trek snacks in Unit 1’s exercise), making a school timetable without clashes, and sudoku on boards of any size.

They all stand or fall together. If anyone finds a fast method for any one of them, there is a fast method for every one, and P = NP. If anyone proves that one of them has none, then none of them has, and P ≠ NP. That is why, in 2000, the Clay Mathematics Institute made P versus NP one of its seven Millennium Prize Problems, with a prize of one million US dollars for a proof either way.

Why it matters

It matters every time you pay by phone. Unit 7’s RSA, which helps keep a payment in a banking or wallet app secret, rests on a problem in NP: multiplying two huge primes is quick, and checking a proposed factor is quick (divide), but nobody knows a fast way to find the factors of the product. If P = NP and the fast method were practical, factoring would be fast, and that protection would fall overnight; so would much of the rest of today’s cryptography. (Factoring is in NP but is not known to be NP-complete: even a proof that P ≠ NP wouldn’t prove that factoring is hard. Its safety rests on fifty years of clever people failing.)

It would not all be bad news. If P = NP with a practical method, computers could find the best school timetable, the best delivery routes and the shortest trek as easily as they check them, and could search for mathematical proofs as easily as they check them. That is what Gödel was asking about. Most experts think this world isn’t ours.

Choose at least two. All can be done on this page, even on a phone (press Edit under a program, change it and press Run); the Turing machines run in the widget below.