Uncomputability

Imagine you were tasked with the mission of finding out which things can and cannot be calculated with a computer, given that you had infinite memory and infinite time.

Given the generality of computers, you might be tempted to say everything, but it turns out that this is not the case.

To begin tackling this problem, we need a formal notion of what it means to compute something. We are going to focus on computing natural functions; that is, functions which transform natural numbers to natural numbers.

As natural numbers can be used to encode pretty much anything, this class of computations is far wider than one might initially think. For example, we can encode finite sequences of arbitrary length of natural numbers in a single natural number, and we can encode words in sequences of numbers.

We are going to say that a computer program computes a certain natural function if on input it returns the result of applying such function to $n$ , for every natural $n$ . We note that programs do not have to halt on inputs; they may just run forever. In that case, we will say that the program is computing a partial function, which is not defined on some inputs.

The diagonal function

We are going to construct a concrete example of a function which is not computable.

Imagine an infinite list of every possible Python program, associated with the infinite outputs each would produce if we feed it the sequence of natural numbers $1, 2, 3, . . .$ .

Thus, we may end up with a table such as this:

program #1: 0->1, 1->X, 2->3,...

program #2:

etc...

Where an X means that the program does not halt on that input or does not return an output, and thus the function it represents is not defined there.

Now, we are going to construct an explicit function which is not computable using this table.

Let $D I A G$ be such that: $D I A G (n) = {\begin{matrix} 1 i f M_{n} (n) = 0 0 i f M_{n} (n) is undefined or defined and greater than 0 \end{matrix}$

The notation $M_{n}$ means "the $n$ th program in our enumeration of programs". Let's see what we have done there. We are looking at the $n$ th entry of every program and saying that this function on input $n$ outputs something different that the $n$ th program. This technique is called diagonalization, and it is ubiquitous in computability and logic.

The function $D I A G$ , known as the diagonal_function, is guaranteed to disagree with every program on at least one input. Thus, there cannot be a program which computes $D I A G$ !

The halting function

The reader may at this point be however not satisfied with such an unnatural example of an uncomputable function. After all, who is going to want to compute such a weird thing? Do not dismay, for there is a much better example: the halting function.

Let $H A L T$ be defined as: $H A L T (n, x) = {\begin{matrix} 1 i f M_{n} (x) halts 0 i f M_{n} (x) does not halt \end{matrix}$

That is, the function $H A L T$ decides whether a given program is going to halt on a particular input. Now that is interesting.

To cite one imaginative use of the halting function, one could for example code a program which on any input simply ignores the input and starts looking for a counterexample of the Collatz conjecture, halting iff it finds one. Then we could use the halting function to see whether the conjecture is true or false.

Sadly, $H A L T$ is not computable. We are going to give two proofs of this fact, one by reduction to the diagonal function and other by diagonalization.

Proof by reduction

Proofs by reduction are quite common in computability. We start by supposing that the function we are dealing with, in this case $H A L T$ , is computable, and then we proceed to use this assumption to show that if that was the case we could compute another function we know is uncomputable.

Suppose we have a program, which we are going to represent by $H A L T$ , which computes the halting function.

Then we could write a program such as this one:

DIAGONAL(n):
    if HALT(n,n):
        return 1 if M_n==0 else return 0
else return 0

Which computes the diagonal function. As we know such a program cannot possibly exist, we conclude by reductio ad absurdum that $H A L T$ is not computable.

Exercise

Prove that $H A L T$ is reducible to $D I A G O N A L$ ; ie, that if $D I A G O N A L$ was computable we could compute $H A L T$ .

Show solution

Suppose we want to know whether the program $P R O G$ halts on input $n$ . Then we first code the auxiliary program:

AUX(x): 
    PROG(n)
    return 0

That is, $A U X$ is the program which on any input first runs $P R O G$ on input $n$ and then outputs $0$ if $P R O G$ ever halts.

Then $D I A G (┌ A U X ┐) == 1$ iff $P R O G$ halts on input $n$ .

Proof by diagonalization

Another nifty proof of uncomputability comes from diagonalization.

As before, let's suppose $H A L T$ is computable. Then we could write a program such as this one:

prog(n):
    if HALT(n,n)==1: 
       loop forever
    else return 0

The program halts on input $n$ iff $M_{n}$ does not halt on input $n$ .

Now, let $┌ p r o g ┐$ represent the number in the list of the program which occupies the $p r o g$ program. Here comes the question: does $p r o g$ halt when its input is $┌ p r o g ┐$ ?

Supposing either yes or no leads to a contradiction, so we conclude that such a program cannot possibly exist, and it follows from the contradiction that $H A L T$ is not computable.

So now you are ready to start your journey through the realm of computability!

Suggested next steps include examining other uncomputable functions such as the busy beaver sequence, or proceeding to complexity theory.

LESSWRONG
LW