Undecidability

The previous lesson split the two-state machine family into three sets: 9784 machines halted, 5040 machines were certified to never halt, and nothing was said about 5912 machines. The existence of the third set may look like a shortfall; this lesson shows that it is not.

To do this, the machine family is set aside and a single rule is examined. The rule is one line and simple enough for a child to understand: if the number is odd, multiply by three and add one; if even, divide by two; stop once the number is 1. The rule has neither branching depth nor a stored state. The gap between the rule’s brevity and the unpredictability of its behavior is this lesson’s entire subject.

A One-Line Rule, Unpredictable Behavior

The measure is set up the same way as in the previous lessons. The budget is the step count, the universe is the set of starting numbers, and how many starting points halt at each budget value is counted cumulatively.

• MC27 — The rule is a single line and carries no option: for a given number, the next number is unique. It is a deterministic rule, containing no randomness.
• MC28 — The universe is the integers from 1 up to an upper limit. In the first measurement, the upper limit is 1000.
• MC29 — The budget is the step count. When the budget runs out, the run is cut off, and the result for that starting point counts as unknown; “does not halt” is not written.
• MC30 — Steps spent are also totaled separately, because a budget’s cost cannot be read unless it sits alongside the result.
• MC31 — The highest of the intermediate values is recorded. The rule’s output is not a straight descent; it grows first.

"""One-line counter rule: sweeping the step budget."""


def counter_run(n, budget):
    """3n+1 if n is odd, n/2 if even. Halts once n = 1."""
    step, highest = 0, n
    while n != 1 and step < budget:
        n = 3 * n + 1 if n % 2 else n // 2
        highest = max(highest, n)
        step += 1
    return {"halted": n == 1, "step": step, "highest": highest}


def budget_sweep(budgets, upper=1000):
    known = set()
    print(f"one-line counter rule, {upper} starting points")
    print("budget  known to halt  unknown  steps spent")
    for b in budgets:
        spent = 0
        for n in range(1, upper + 1):
            r = counter_run(n, b)
            spent += r["step"]
            if r["halted"]:
                known.add(n)
        print(f"{b:5d}  {len(known):15d}  {upper - len(known):10d}  {spent:13d}")


budget_sweep((5, 20, 50, 100, 200))
longest = max(range(1, 1001), key=lambda n: counter_run(n, 1000)["step"])
r = counter_run(longest, 1000)
print(f"longest run: n = {longest} -> {r['step']} steps ,"
      f" highest intermediate value {r['highest']}")

one-line counter rule, 1000 starting points
budget  known to halt  unknown  steps spent
    5                7         993           4985
   20              155         845          19159
   50              569         431          37815
  100              756         244          54426
  200             1000           0          59542
longest run: n = 871 -> 178 steps , highest intermediate value 190996

Three numbers side by side. Budget: 5, 20, 50, 100, 200 steps. What the budget answers: the number of settled starting points is 7, 155, 569, 756, and 1000. What the budget fails to answer: 993, 845, 431, 244, and finally 0 starting points.

In the previous lesson’s machine family, growing the budget changed nothing past step 6. Here the opposite happens: as the budget rises 40-fold, the number of settled starting points rises from 7 to 1000, a 142-fold increase. Growing the budget sometimes changes nothing, sometimes everything, and which one it is can only be seen by measuring. The cost was measured too: from 4985 steps to 59,542, a twelvefold increase.

The last line shows why the rule is unpredictable. The longest run, for n=871, takes 178 steps, and the intermediate value in that run climbs to 190,996. That is, a sequence starting at 871 rises to 219 times its starting value before dropping to 1. The rule itself is one line; its behavior jumps this much depending on the starting point.

And right here, the lesson’s most important sentence must be written. All 1000 of 1000 starting points halting is not proof that all of them will halt. The table says only this: each of the thousand starting points tried dropped to 1 in at most 200 steps. It says nothing about the ones not tried, and the next section shows with a number that this is not an idle worry.

Same Budget, Different Universe

A budget being “sufficient” is not a property of the budget. In the first lesson, this was measured by three-state automata recognizing every language at length limit 1 and half in a million at length limit 4. The same measure is repeated here: the budget is held fixed, the universe is grown.

• MC32 — The universe sweep sets the upper limit to 1000, 2000, and 5000. The budget is fixed at 200.
• MC33 — A bounded decider is a procedure that says “does not halt” when the budget runs out. This procedure can be wrong, and the starting point where it is wrong is found by searching.
• MC34 — That a starting point halts can also be shown by proof: if the number is a power of two, it is halved on every step and drops to 1 in a number of steps equal to the exponent. This is not a run result but a reading of the rule.

"""Same budget, different universe: adequacy is not a property of the budget."""


def counter_run(n, budget):
    step = 0
    while n != 1 and step < budget:
        n = 3 * n + 1 if n % 2 else n // 2
        step += 1
    return n == 1


print("budget 200, universe sweep")
print("  upper  known to halt  unknown")
for upper in (1000, 2000, 5000):
    b = sum(1 for n in range(1, upper + 1) if counter_run(n, 200))
    print(f"{upper:5d}  {b:15d}  {upper - b:10d}")
print()
print("smallest starting point that fools each budget")
for budget in (5, 20, 50, 100, 200, 300):
    n = 1
    while counter_run(n, budget):
        n += 1
    print(f"  budget {budget:4d} -> n = {n}")
print()
powers = [n for n in range(1, 1001) if n & (n - 1) == 0]
print("settled by certificate: powers of two")
print("  up to 1000,", len(powers), "starting points ,",
      "test is a single comparison, longest run",
      max(len(bin(n)) - 3 for n in powers), "steps")
print("  do they all really halt:",
      all(counter_run(n, 1000) for n in powers))

budget 200, universe sweep
  upper  known to halt  unknown
 1000             1000           0
 2000             2000           0
 5000             4991           9

smallest starting point that fools each budget
  budget    5 -> n = 3
  budget   20 -> n = 25
  budget   50 -> n = 27
  budget  100 -> n = 27
  budget  200 -> n = 2463
  budget  300 -> n = 26623

settled by certificate: powers of two
  up to 1000, 10 starting points , test is a single comparison, longest run 9 steps
  do they all really halt: True

The first table breaks the previous section’s result. Budget 200 suffices for a thousand out of a thousand starting points, and two thousand out of two thousand; at five thousand starting points, it fails to settle 9 of them. The sentence “budget 200 suffices” tells nothing without the universe being written.

The second table is sharper. For every budget, a starting point was found that fools the decider working with that budget: 3 for budget 5, 25 for budget 20, 27 for budget 100, 2463 for budget 200, 26,623 for budget 300. The fooling starting point moves farther away as the budget grows, but it does not disappear. What the measurement says is exactly this: for all six of the six budgets tried, a counterexample was found. That such an example exists for every budget cannot be drawn from this table; that is the theory’s job, not the measurement’s.

The third block shows information coming from an entirely different source. For powers of two, halting is known without running: every step halves the number, and it drops to 1 in a number of steps equal to the exponent. This proof is tested with a single comparison and covers 10 starting points up to 1000. The run, by contrast, covers 1000 starting points by spending 59,542 steps. The proof is cheap and narrow, the run is expensive and wide; the two give different kinds of information, and neither stands in for the other. The cheap test in the Advanced Algorithms course also worked in only one direction; the one here is the same.

Two Answers and Three Answers

A bounded decider has two designs, and the difference between them can be measured. The first says “does not halt” when the budget runs out, and produces an answer for every starting point. The second says “unknown” when the budget runs out, and leaves some starting points without an answer. The two do exactly the same run, spend the same steps; the only place they differ is the sentence at the moment the budget runs out.

• MC35 — The reference answer is taken from a 100,000-step budget. Because every starting point in this universe halts under 300 steps, the reference is certain for this universe; the same cannot be said for a larger universe.
• MC36 — The wrong count is the number of starting points where the decider’s answer diverges from the reference. “Unknown” does not count as an answer, and is not counted as wrong.

"""Comparing a two-answer decider with a three-answer one in the same universe."""


def counter_run(n, budget):
    step = 0
    while n != 1 and step < budget:
        n = 3 * n + 1 if n % 2 else n // 2
        step += 1
    return n == 1, step


def two_answer(n, budget):
    """Says 'halts' or 'does not halt' when the budget runs out. Can be wrong."""
    halted, _ = counter_run(n, budget)
    return "halts" if halted else "does not halt"


def three_answer(n, budget):
    """Says 'unknown' when the budget runs out. Never wrong, but does not always answer."""
    halted, _ = counter_run(n, budget)
    return "halts" if halted else "unknown"


UPPER = 5000
truth = {n: counter_run(n, 100000)[0] for n in range(1, UPPER + 1)}
print(f"universe {UPPER} starting points, true answer taken from a 100000-step run")
print("budget  two-answer: wrong  three-answer: wrong  unknown  steps spent")
for budget in (5, 20, 50, 100, 200, 300):
    wrong2 = wrong3 = unknown = spent = 0
    for n in range(1, UPPER + 1):
        spent += counter_run(n, budget)[1]
        a2, a3 = two_answer(n, budget), three_answer(n, budget)
        if (a2 == "halts") != truth[n]:
            wrong2 += 1
        if a3 == "unknown":
            unknown += 1
        elif (a3 == "halts") != truth[n]:
            wrong3 += 1
    print(f"{budget:5d}  {wrong2:19d}  {wrong3:20d}  {unknown:10d}  {spent:13d}")

universe 5000 starting points, true answer taken from a 100000-step run
budget  two-answer: wrong  three-answer: wrong  unknown  steps spent
    5                 4993                     0        4993          24985
   20                 4758                     0        4758          98948
   50                 3110                     0        3110         218633
  100                 1666                     0        1666         332345
  200                    9                     0           9         387867
  300                    0                     0           0         387968

Same budget, same run, same steps — two separate outcomes. The two-answer design is wrong on 4993 starting points at budget 5; 9 at budget 200, 0 at budget 300. The three-answer design is never wrong at any budget: the wrong column reads 0 in all six rows. The price it pays is the starting points it leaves unanswered, and this number is exactly the same as the wrong column’s. So the third answer is not a loss of information; it is giving the wrong answer its correct name.

The last column says one more thing. As the budget rises from 200 to 300, steps spent rise from 387,867 to 387,968, an increase of only 101 steps — because only 9 starting points exceed 200 steps. The cost of closing the remaining uncertainty is three in ten thousand, next to the whole budget spent up to that point. Not closing uncertainty where it closes cheaply is a design flaw; but that it is cheap in this universe does not mean it will be cheap in every universe.

Why the Halting Problem Is Undecidable

Everything measured so far was for a single rule. The halting problem is more general than this: given a program’s description and a given input, saying whether that program will halt. That this problem is undecidable is a proven result of the theory, and the sketch below is the shape of that proof; no run in this lesson establishes it.

Suppose there is a decide procedure that gives the correct answer for every program description and every input. Then a second procedure can be written: opposite, which takes a description it is given, calls decide on that description, giving the description itself as the input; if the answer is “halts,” it loops forever, if the answer is “does not halt,” it halts immediately. Now let opposite be called with its own description. If decide says “halts,” opposite starts looping, meaning it does not halt. If it says “does not halt,” opposite halts immediately. In both cases, the assumed procedure has given the wrong answer. Since the assumption produces a contradiction, no such procedure exists.

The power of this proof is that it appeals to no budget at all. In the previous section, a counterexample was searched for and found for every budget; the proof, on the other hand, does not search — it shows that a single procedure cannot exist. The thesis cited in the previous lesson is useful here: the result does not concern a single model, but the concept of “procedure” itself, because the thesis binds every reasonable model to the same set.

The engineering counterpart of this result is: for a large portion of questions about a program’s behavior, there is no procedure that gives the correct answer for every program. Whether two programs give the same output, that a piece of code will never run, that a loop will terminate — all of these contain the halting problem, and all fall under the scope of the same result. This does not mean analysis tools are useless; what it says is that such a tool has to give three answers, not two. The previous lesson’s three-way split into halted, loop, and unknown was exactly this, and that third set is not an arbitrary shortfall — it is the result itself.

One of the two debts left by the Advanced Algorithms course was paid here. For some questions, not knowing the answer can be a fact about the problems rather than about our knowledge, and the halting problem is the proven example of this. The second debt — why nothing better than brute force is known — is still open: what is asked there is not whether a problem can be solved, but how fast it can be solved.

Summary

• On the one-line counter rule, of 1000 starting points, 7 are settled at budget 5, 155 at 20, 569 at 50, 756 at 100, and 1000 at 200; steps spent rise from 4985 to 59,542.
• The longest run, for n=871, takes 178 steps and the intermediate value rises to 190,996; the rule is one line, the behavior is unpredictable.
• All 1000 of 1000 starting points halting is not proof that all of them will halt.
• The same budget of 200 settles all starting points at 1000 and 2000, but fails to settle 9 of them at 5000; for all six of the six budgets tried, a fooling starting point was found.
• A proof is cheap and narrow: halting for powers of two is known with a single comparison and covers 10 starting points up to 1000; a run covers 1000 starting points with 59,542 steps.
• That the halting problem is undecidable is a result of the theory, not of a run; the result’s practical counterpart was measured: a two-answer decider is wrong 4993 times at budget 5 across 5000 starting points, while the three-answer design doing the exact same run has a wrong count of zero at all six budgets.

Next Step

The Models of Computation topic showed one side of the limit: for some questions, the answer cannot be given by any procedure at all. The next topic takes up the other side. There, every problem will be decidable, and the only question will be in how many steps. Complexity Classes takes on the second debt left by the Advanced Algorithms course, and first builds the easiest class: decision problems solvable in polynomial time.