The Halting Problem And Provability

As a general matter, the question of whether or not a UTM will halt when given an input $x$ , is not computable, in that there is no single program that can say ex ante, whether or not $U(x)$ will halt, or run forever. We can restate this, if we iterate the value of $x$ as a binary number, beginning with $1$ , and continuing on, and asking the question of whether or not $U(x)$ will halt. We know this is not decidable in general, but it must be the case for each $x \in \mathbb{N}$ that $U(x)$ will either halt or run forever. This implies an infinite set of mathematical facts that are unknowable, as a general matter, and will instead require the passing of an arbitrary amount of time.

Now consider the question of whether you can prove that $U(x)$ will halt for a given $x$ , without running $U(x)$ . The Halting Problem does not preclude such a possibility, it instead precludes the existence of a generalized program that can say ex ante whether or not $U(x)$ will halt as a general matter. For example, consider the function $F(x) = x^2$ , for all $x \in \mathbb{N}$ . We can implement $F(x)$ in for example C++, and this will require exactly one operation, for any given input, and because C++ is a computable language, there must be some input to a UTM that is equivalent to $F(x)$ , for all $x \in \mathbb{N}$ . As a consequence, we have just proven that an infinite set of inputs to a UTM will halt, without running a single program.

This leads to a set of questions:

1. If you can prove that a program $P$ will halt over some infinite subset of $\mathbb{N}$ , and not halt for any other natural number, is there another program $R$ that will report 1 or 0, for halting or not halting, respectively.

2. If you can prove that a program $P$ will halt over some infinite subset of $\mathbb{N}$ , and not halt for any other natural number, is there another program $R$ that will report 1 or 0, for halting or not halting, respectively, without running $P$ or any equivalent program (as defined below).

3. If you can prove that a program $P$ (and all equivalent programs, as defined below) will halt over some infinite subset of $\mathbb{N}$ , and not halt for any other natural number, is there another program $R$ that can provide a proof (in either human, machine, or symbolic language) that this is the case, for all equivalent programs (as defined below).

A program $A$ is equivalent to program $B$ if $A(x) = B(x)$ for all $x \in \mathbb{N}$ .

Note the existence of a single case where there is a proof, without a corresponding program $R$ , would be proof that the human being that generated the proof is non-computable, and therefore, physics is non-computable.

Discover more from Information Overload

Subscribe to get the latest posts sent to your email.

Discover more from Information Overload

Share this:

Related

Leave a comment Cancel reply