# 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):
return 1 if M_n==0 else return 0
else return 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)
return 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 forever
else return 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.

• This can be for­mat­ted bet­ter. Also I think there is a typo with else 0?

• @1 I was aiming for the Python syn­tax of the ternary op­er­a­tor, but I am still quite un­fa­mil­iar with Ar­bital and I do not know how to for­mat it nicely.

Also, is quite a funny situ­a­tion that even though I am the cre­ator and main­tainer I do not have priv­ileges to edit the page. Is that in­ten­tional?

• Oh no! That’s a bug, we are look­ing into it…

• Oh, not at all. Prob­a­bly a bug; I’m go­ing to look into it right now.

• Should be fixed. Try now.