Computable problems and the Halting problem

Non-computable problems, the Halting problem and why it cannot be solved, and what step limits can and cannot tell you.

A6.8Theory of computationA level20 min

The last lesson's limit was time: intractable problems can be solved, just not quickly. This lesson's limit is harder. Some problems cannot be solved by any algorithm, on any computer, however fast, given as long as you like. In 1936 Alan Turing proved that one of the most useful problems imaginable is like this.

Computable and non-computable

A problem is computable (or decidable) if there is an algorithm that, for every possible input, finishes after a finite number of steps with the correct answer. Sorting a list is computable. So is the travelling salesman problem: brute force always finishes, eventually.

A problem is non-computable if no such algorithm can exist. This is not a statement about today's computers or today's programmers. It is proved mathematically that no algorithm can ever solve every case.

Lesson A6.3 gave a hint that non-computable problems must exist. Every program is a finite string of characters, so the set of all programs is countably infinite. The set of all yes or no problems about whole numbers is so much bigger that it is not countable. There are not enough programs to go round.

The Halting problem

Some programs finish (they halt); some run forever. A loop like while x != 0: x = x - 4 halts when x starts at 8 but never when it starts at 10. It would be extremely useful to have a checker that could look at any program and its input and say, without running it forever, whether it will halt. Every infinite-loop bug would be caught before the program shipped.

The Halting problem: is it possible, in general, to write a program that can tell, given any program and any input, whether that program will halt when run with that input, without running it?

Turing proved the answer is no. The Halting problem is non-computable.

Why no halting checker can exist

The proof is by contradiction. Suppose someone has written a function halts(program, data) that always returns True if program would halt when given data, and False if it would run forever. Programs are just text, so a program can be given to itself as its data. Now write this:

def halts(program, data):
    # suppose this always answers correctly, and always finishes
    ...

def contrary(program):
    if halts(program, program):
        while True:          # halts says it halts, so loop forever
            pass
    else:
        return               # halts says it loops, so stop at once

What happens when contrary is given its own code, contrary(contrary)?

• If halts(contrary, contrary) returns True, it is claiming contrary(contrary) halts. But then contrary loops forever. The answer was wrong.
• If it returns False, it is claiming contrary(contrary) runs forever. But then contrary returns at once. Wrong again.

Either way halts gives the wrong answer for this input, so a correct halts cannot exist. Nothing about the proof depends on how clever halts is or how fast the computer is.

What it means in practice

• Some problems cannot be solved by computer at all. The Halting problem was the first shown, and many others follow from it: for example, whether two programs always give the same output, or whether a program ever reaches a particular line.
• Tools have to approximate. A compiler that warns "this code is unreachable" or an analyser that flags a possible infinite loop is right for many cases, but no tool can be right for all of them. They answer "yes", "no" or "cannot tell".
• Running a program is not a way round it. Running a program for a while can prove it halts, when it does. It can never prove it runs forever: it might stop on the very next step.

That last point is how BugBot's simulator deals with it. Every task has a time limit, and a program still going at the end is stopped. The simulator does not decide that the program would never have finished; it just stops waiting.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def steps_to_one(n, limit):
    # the Collatz rule: halve if even, otherwise 3n + 1; stop at 1
    steps = 0
    while n != 1:
        if steps == limit:
            return None
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps = steps + 1
    return steps

for start in [6, 7, 27]:
    print(start, steps_to_one(start, 1000))

Run this in the simulator

Every starting number anyone has ever tried reaches 1 (27 takes 111 steps), but nobody has proved that all of them do. A step limit gives a real answer for the ones that finish and an honest "don't know" otherwise.

Task: the watchdog

Write a watchdog that runs simple programs with a step limit and reports honestly on each.

• Each program in programs is a tuple (name, x, step, done): name is a string, x is the starting whole number, step(x) returns the next value of x, and done(x) returns True when the program has halted.
• Write watch(name, x, step, done, limit). Before each step, check done(x). If it is True, print <name>: halted after <n> steps, where n is the number of steps taken so far, and stop watching. Otherwise take a step. If limit steps have been taken and done(x) is still not True, print <name>: no answer after <limit> steps.
• Call watch for each program in order, with limit set to 1000.

Three lines in all, such as p1: halted after 3 steps. Work the counts out by running the programs, not by hand.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

programs = [
    ("p1", 10, lambda x: x - 3, lambda x: x == 1),
    ("p2", 10, lambda x: x - 4, lambda x: x == 0),
    ("p3", 27, lambda x: x // 2 if x % 2 == 0 else 3 * x + 1, lambda x: x == 1),
]

def watch(name, x, step, done, limit):
    pass

Challenges

1. Program p2 never halts. Prove it by thinking about the values x takes, not by running it.
2. A program whose x can only take a few different values must either halt or repeat a value. Add a check to watch that prints loops forever when a value repeats. Why does this not solve the Halting problem?
3. Explain the difference between "intractable" and "non-computable" to someone who thinks a faster computer fixes both.