# Connecting the halting problem and induction

Suppose we have a program $$\mathbf{H}(p, x)$$ that solves the halting problem for any program $$p$$ evaluated on input $$x$$, returning $$\mathrm{True}$$ if the program halts and $$\mathrm{False}$$ otherwise. Consider statements of the form $$\forall n \in \mathbb{N}: A(n)$$, where $$A$$ is some proposition that can be easily evaluated for any particular natural number. Let $$p(A)$$ be the following program:

i = 1
loop forever:
if not A(i):
return
i += 1


Then the evaluation of $$\neg\mathbf{H}(p, A)$$ constitutes a proof of the truth or falsehood of the statement $$A$$ for all natural numbers, if the evaluation of $$A(n)$$ is guaranteed to halt. Essentially, the halting function $$\mathbf{H}$$ automatically performs the process of mathematical induction.

When $$A(n)$$ is sufficiently simple, for instance $$n \leq 2^n$$, we can just perform the induction manually, and there’s no reason to invoke the halting function $$\mathbf{H}$$. But what if checking $$A(n)$$ involves a procedure that may not halt? Let’s try to apply the method to Fermat’s Last Theorem: $$\forall n > 2, \forall a, b, c \in \mathbb{Z} : a^n + b^n \neq c^n$$ First, we have find out how to evaluate the statement for any given $$n$$. Let $$\mathbb{Z}^3$$ be the countably infinite set of triples of integers, and let $$I(n):\mathbb{N} \rightarrow \mathbb{Z}^3$$ be an enumeration of the set of triples. Let $$A(n)$$ be the following procedure:

j = 1
loop forever:
x, y, z = I(j)
if x^n + y^n == z^n:
return False
j += 1
return True // never executed


This procedure halts only if it finds a counterexample for a particular value of $$n$$. Suppose we try to apply the program $$p$$ that we defined above. If the condition $$x^n + y^n = z^n$$ is not true for any integers given a particular value of $$n$$, $$A(n)$$ doesn’t halt, so $$p$$ (which invokes $$A$$) also fails to halt. For example, if $$A(3)$$ does not halt, the values $$n > 3$$ are never checked. Then the value of $$\neg \mathbf{H}(p, A)$$ is equivalent to $$\exists n \in \mathbb{N}: A(n)$$ rather than the desired $$\forall n \in \mathbb{N}: A(n)$$.

As it turns out, we can solve this by invoking $$\mathbf{H}$$ again. Take a look at the following program, $$q(A)$$:

i = 3 // because the theorem says n > 2
loop forever:
if H(A, i):
return
i += 1


Instead of using a Boolean return value, we can define $$A$$ such that it halts if and only if the statement is false, and use the power of $$\mathbf{H}$$ to immediately check an infinity of cases. Now, the expression $$\neg \mathbf{H}(q, A)$$ constitutes a proof of Fermat’s Last Theorem. A similar argument can be used for many difficult problems over the natural numbers; for instance, the Collatz conjecture can be solved by constructing $$A$$ to evaluate, term-by-term, the Collatz sequence of a number. By employing a few dumb tricks, a computer with super-Turing capabilities could prove almost any theorem over the natural numbers, including many that have stumped the best of us for centuries.

I think this is a pretty strong argument in favor of the Church-Turing thesis,1 which states that a function that Turing machines cannot compute cannot be evaluated by any method whatsoever. That is to say, the function $$\mathbf{H}$$ cannot be physically instantiated, because the universe does not allow it.

1. Technically, this is the converse of the CTT; see the Stanford philosophy page ↩︎

If you liked this post, you might like my current project, AGI notes. You can also follow me on Twitter.