Uncomputability

Imag­ine you were tasked with the mis­sion of find­ing out which things can and can­not be calcu­lated with a com­puter, given that you had in­finite mem­ory and in­finite time.

Given the gen­er­al­ity of com­put­ers, you might be tempted to say ev­ery­thing, but it turns out that this is not the case.

To be­gin tack­ling this prob­lem, we need a for­mal no­tion of what it means to com­pute some­thing. We are go­ing to fo­cus on com­put­ing nat­u­ral func­tions; that is, func­tions which trans­form nat­u­ral num­bers to nat­u­ral num­bers.

As nat­u­ral num­bers can be used to en­code pretty much any­thing, this class of com­pu­ta­tions is far wider than one might ini­tially think. For ex­am­ple, we can en­code finite se­quences of ar­bi­trary length of nat­u­ral num­bers in a sin­gle nat­u­ral num­ber, and we can en­code words in se­quences of num­bers.

We are go­ing to say that a com­puter pro­gram com­putes a cer­tain nat­u­ral func­tion if on in­put \(n\) it re­turns the re­sult of ap­ply­ing such func­tion to \(n\), for ev­ery nat­u­ral \(n\). We note that pro­grams do not have to halt on in­puts; they may just run for­ever. In that case, we will say that the pro­gram is com­put­ing a par­tial func­tion, which is not defined on some in­puts.

knows-req­ui­site(Un­countabil­ity): Now, the first thing to no­tice is that the set of pos­si­ble func­tions from \(\mathbb{N}\) to \(\mathbb{N}\) is not enu­mer­able, while the set of pos­si­ble pro­grams, which are finite se­quences of a finite quan­tity of sym­bols, is enu­mer­able. Thus, there can­not be a one-to-one cor­re­spon­dence be­tween func­tions and pro­grams; there must nec­es­sar­ily ex­ist a func­tion which is not com­puted by any pro­gram.

So com­put­ers can­not com­pute ev­ery­thing! <div>


The di­ag­o­nal function

We are go­ing to con­struct a con­crete ex­am­ple of a func­tion which is not com­putable.

Imag­ine an in­finite list of ev­ery pos­si­ble Python pro­gram, as­so­ci­ated with the in­finite out­puts each would pro­duce if we feed it the se­quence of nat­u­ral num­bers \(1,2,3,...\).

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

pro­gram #1: 0->1, 1->X, 2->3,…

pro­gram #2:

etc…

Where an X means that the pro­gram does not halt on that in­put or does not re­turn an out­put, and thus the func­tion it rep­re­sents is not defined there.

Now, we are go­ing to con­struct an ex­plicit func­tion which is not com­putable us­ing this table.

Let \(DIAG\) be such that:

$$ DIAG(n) = \left\{ \begin{array}{lr} 1\ if\ M_n(n) = 0\\ 0\ if\ M_n(n)\mbox{ is undefined or defined and greater than 0} \end{array} \right. $$

The no­ta­tion \(M_n\) means “the \(n\)th pro­gram in our enu­mer­a­tion of pro­grams”. Let’s see what we have done there. We are look­ing at the \(n\)th en­try of ev­ery pro­gram and say­ing that this func­tion on in­put \(n\) out­puts some­thing differ­ent that the \(n\)th pro­gram. This tech­nique is called di­ag­o­nal­iza­tion, and it is ubiquitous in com­putabil­ity and logic.

The func­tion \(DIAG\), known as the di­ag­o­nal func­tion, is guaran­teed to dis­agree with ev­ery pro­gram on at least one in­put. Thus, there can­not be a pro­gram which com­putes \(DIAG\)!


The halt­ing function

The reader may at this point be how­ever not satis­fied with such an un­nat­u­ral ex­am­ple of an un­com­putable func­tion. After all, who is go­ing to want to com­pute such a weird thing? Do not dis­may, for there is a much bet­ter ex­am­ple: the halt­ing func­tion.

Let \(HALT\) be defined as:

$$ HALT(n,x) = \left\{ \begin{array}{lr} 1\ if\ M_n(x)\mbox{ halts}\\ 0\ if\ M_n(x)\mbox{ does not halt } \end{array} \right. $$

That is, the func­tion \(HALT\) de­cides whether a given pro­gram is go­ing to halt on a par­tic­u­lar in­put. Now that is in­ter­est­ing.

To cite one imag­i­na­tive use of the halt­ing func­tion, one could for ex­am­ple code a pro­gram which on any in­put sim­ply ig­nores the in­put and starts look­ing for a coun­terex­am­ple of the Col­latz con­jec­ture, halt­ing iff it finds one. Then we could use the halt­ing func­tion to see whether the con­jec­ture is true or false.

Sadly, \(HALT\) is not com­putable. We are go­ing to give two proofs of this fact, one by re­duc­tion to the di­ag­o­nal func­tion and other by di­ag­o­nal­iza­tion.

Proof by reduction

Proofs by re­duc­tion are quite com­mon in com­putabil­ity. We start by sup­pos­ing that the func­tion we are deal­ing with, in this case \(HALT\), is com­putable, and then we pro­ceed to use this as­sump­tion to show that if that was the case we could com­pute an­other func­tion we know is un­com­putable.

Sup­pose we have a pro­gram, which we are go­ing to rep­re­sent by \(HALT\), which com­putes the halt­ing func­tion.

Then we could write a pro­gram such as this one:

DIAGONAL(n):
    if HALT(n,n):
        re­turn 1 if M_n==0 else re­turn 0
else re­turn 0

Which com­putes the di­ag­o­nal func­tion. As we know such a pro­gram can­not pos­si­bly ex­ist, we con­clude by re­duc­tio ad ab­sur­dum that \(HALT\) is not com­putable.

Exercise

Prove that \(HALT\) is re­ducible to \(DIAGONAL\); ie, that if \(DIAGONAL\) was com­putable we could com­pute \(HALT\).

Sup­pose we want to know whether the pro­gram \(PROG\) halts on in­put \(n\). Then we first code the aux­iliary pro­gram:

AUX(x): 
    PROG(n)
    re­turn 0

That is, \(AUX\) is the pro­gram which on any in­put first runs \(PROG\) on in­put \(n\) and then out­puts \(0\) if \(PROG\) ever halts.

Then \(DIAG(\ulcorner AUX\urcorner)==1\) iff \(PROG\) halts on in­put \(n\). <div><div>

Proof by diagonalization

Another nifty proof of un­com­putabil­ity comes from di­ag­o­nal­iza­tion.

As be­fore, let’s sup­pose \(HALT\) is com­putable. Then we could write a pro­gram such as this one:

prog(n):
    if HALT(n,n)==1: 
       loop for­ever
    else re­turn 0

The pro­gram halts on in­put \(n\) iff \(M_n\) does not halt on in­put \(n\).

Now, let \(\ulcorner prog\urcorner\) rep­re­sent the num­ber in the list of the pro­gram which oc­cu­pies the \(prog\) pro­gram. Here comes the ques­tion: does \(prog\) halt when its in­put is \(\ulcorner prog \urcorner\)?

Sup­pos­ing ei­ther yes or no leads to a con­tra­dic­tion, so we con­clude that such a pro­gram can­not pos­si­bly ex­ist, and it fol­lows from the con­tra­dic­tion that \(HALT\) is not com­putable.


So now you are ready to start your jour­ney through the realm of com­putabil­ity!

Suggested next steps in­clude ex­am­in­ing other un­com­putable func­tions such as the busy beaver se­quence, or pro­ceed­ing to com­plex­ity the­ory.

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.