The halting problem and limits of computing

The halting problem asks whether a given program will ever stop on a given input. Alan Turing proved in 1936 that no program can answer it correctly for every program.

A second limit is time. Some problems can be solved, but only in more time than you have. This lesson separates the impossible from the merely too slow.

Suppose someone writes halts(program, data), a checker that always answers True if the program stops and False if it runs for ever.

We can use it to build a troublemaker that does the opposite of what the checker predicts about it. Ask the checker about the troublemaker running on itself, and it cannot be right.

# Suppose halts(program, data) always answered True or False correctly.
def troublemaker(program):
    if halts(program, program):
        while True:
            pass
    return "stopped"

# Now ask: does troublemaker stop when given itself?

Running a program tells you when it stops. It never tells you that it never will, because there is always one more second to wait.

The Run below gives sleep five seconds, but the timeout command gives up after one. Giving up is a decision, not an answer.

timeout 1 sleep 5 || echo gave up after one second

In subset sum you are given some numbers and a target. Brute force tries every subset and adds it up.

With n numbers there are 2 to the power n subsets, because each number is either in or out. One more number doubles the work. Run the demo, then add a number and watch the count.

# Brute force: try every subset of the numbers, counting how many we try.
numbers = [3, 5, 8]
target = 8
n = len(numbers)
tried = 0
found = []
for pattern in range(2 ** n):
    total = 0
    chosen = []
    for i in range(n):
        # Bit i of the pattern says whether number i is in this subset.
        if (pattern // (2 ** i)) % 2 == 1:
            total = total + numbers[i]
            chosen.append(numbers[i])
    tried = tried + 1
    if total == target:
        found.append(chosen)
print("subsets tried:", tried)
print("subsets that add up to", target, ":", found)
# Add 13 to numbers and run again: how many subsets are tried now?

python3 -c "print(2 ** 20, 2 ** 40)"

python3 -c "print(2 ** 60 // 10 ** 9 // 31536000)"

Checking an answer to subset sum is quick, but finding one seems to need a search. Whether a quick way to find one exists is a famous open question, called P versus NP.

Write down two other puzzles where checking an answer is easy and finding one looks hard, such as a sudoku.