Proof of the Halting Problem's Unsolvability

[Stoney Pete]

Hi everybody,

I've been trying to understand the various proofs for the unsolvabilty of the Halting Problem, and I was wondering wether the following somewhat informal reconstruction of one the usual proof strategies is by and large correct. I'd like to get your opinion on this, not just concerning the reasoning but also concerning its overall clarity and the terminology used. Here it goes:

Let A₀, A₁, A₂,... be an enumeration of all possible algorithms.

Then the Halting Problem is the question: Is there an algorithm H(m,n) that decides for each algorithm A_m whether A_m gives an output (i.e. halts) when given n as input (with m and n from ℕ)? In other words: is the Halting Problem algorithmically solvable?

So H must be such that it says "yes" when A_m halts on input n, and "no" otherwise. Let's encode: "yes" = 0 and "no" = 1. So we get H(m,n)=0 if A_m(n) is defined, and H(m,n)=1 if A_m(n) is undefined.

Now suppose, for reductio, that H exists. Then the self-halting problem must be algorithmically solvable as well.

Here "self-halting" indicates the situation where any algorithm A_m halts when fed its own number on the list, m, as input. Since H(m,n) decides algorithmically for any A_m whether it halts for input n, with both m and n from ℕ, H must do this also when m=n. That is: H must also decide algorithmically whether A_m self-halts.

Now we can show that the self-halting problem is not algorthmically solvable.

For if H exists, then the compound algorithm D exists as well. D is composed of H and a trivial algorithm L which goes goes into an infinite loop when fed 0 as input, and which outputs 1 when fed 1 as input. To be more precise: D(m,n) = L(H(m,n)).

So if A_m halts on input n, then H(m,n) will output 0, and 0 will then be fed as input to L, causing D to go into a loop (and thus not to halt). And if A_m does not halt on input n, then H(m,n) will output 1, causing L and thereby D to output 1 (and thus to halt).

Now, supposing that H is a possible algorithm, then D is a possible algorithm as well (after all, L is trivially possible; so D=L(H) must be possible as well). So then D must be somewhere on our list of possible algoritms; let's say it's numer d on the list.

To repeat: if H exists, it must also solve the self-halting problem. Thus H must also decide whether D halts when given d as input. That is: H(d,d) must be defined.

But we can see that the execution of H(d,d) leads to contradiction, for the following reasons.

Remember: H(d,d) decides whether D halts on input d. Now there are only two possibilities:

Either D(d) is defined (i.e. D halts on d). Then H(d,d)=0. But D is so constructed that when H outputs 0, D goes into a loop. So if D halts on d, then it doesn't halt. Contradiction.

Or D(d) is not defined, i.e. D does not halt on d. Then H(d,d)=1. But D is so constructed then when H outputs 1, D outputs 1 as well and therefore halts. So if D doen't halt on d, it does halt. Again a contradiction.

So the self-halting problem is not algorithmically solvable.

Thus H cannot decide whether D will self-halt. But IF the Halting Problem is algorithmcally solvable (i.e. if H is possible), THEN the self-halting problem must be algorithmically solvable as well. But we just saw that the consequent of this conditial is false. Therefore the antecedent must be false as well: the Halting Problem is algorithmically unsolvable.

 

[Stoney Pete]

It seems to me, on second thought, that the detour through the self-halting problem is not really necessary. For if we have H, then we automatically have D as well. Then, on the assumption that d is the number of D on the list of all A's, we can ask is H(d,n) is defined for any n from ℕ. And then, too, contradictions arise.

If D(n) is defined, then H(d,n)=0. But then D goes into a loop, and H(d,n)=1. And if D(n) is not defined, then H(d,n)=1. But then D outputs 1 and thus halts, so that H(d,n)=0.

So the proof sketch I gave earlier can actually be more concise, since the self-halting problem is not really necessary...

 

[nomadreid]

You asked whether the exposition was clear. This of course depends on your audience. I will be nitpicky to point out that when you say that D= L(H), this is a little sloppy, because you make it look as if L is a function acting on H, instead of D(.)=L(H(.)), or D ≡ L_°H , or some such. This is a nuance, but potentially confusing.

 

[SSequence]

You asked whether the exposition was clear. This of course depends on your audience. I will be nitpicky to point out that when you say that D= L(H), this is a little sloppy, because you make it look as if L is a function acting on H, instead of D(.)=L(H(.)), or D ≡ L_°H , or some such. This is a nuance, but potentially confusing.

Agreed with this.

Another thing is that when you say "enumeration of all possible algorithms". There are two issues here:
(1) Many people seem to take the notion that an algorithm must halt on all possible inputs. So, by that convention, it would more or less seem that only "total" functions can qualify as algorithms (if this convention was by-passed then probably I think your phrase should be OK). Therefore it might be better to use the phrase "enumeration of all partial recursive functions".

(2) Computer Scientists seem to use the term "algorithm" more or less in an informal manner. The question of when two different programs (say computing exactly the same function) represent the same or different algorithm is known to have not any satisfactory answer currently.
Of possible interest:
https://arxiv.org/abs/0811.0811
http://www.math.lsa.umich.edu/~ablass/abs.pdf

 

[Stoney Pete]

Thanks for the comments, they were helpful. When I began with the enumeration of all possible algorithms, I was indeed supposing that an algorithm need not halt on every input in order to be an algorithm. This seems to be the standard way of thinking about algorithms. Hence the standard phrasing of the Halting problem: is there an algorithm for deciding whether any algorithm A will halt on input n (which implies that A is still an algorithm even if it doesn't halt on n).

But the standard terminology can indeed be confusing... There seems to be no generally accepted term that designates an algorithm that computes a total function. Perhaps the term "effective algorithm" might do the trick? I also see on the net that "total function" is sometimes used...

Also I would like to get your opinion on the following reconstruction of the diagonalization proof for the undecidability of the Halting problem. Here I go a bit faster than in the previous reconstruction. This time I am just concerned with basic validity.

Assuming that H exists, we can algorithmically list all computable real numbers between 0 and 1.

A computable real number is a number whose infinite decimal expansion can be generated by some effective algorithm, so an algorithm that gives a numeral output for every input n from N. If we have H, we can separate all effective algorithms from those that only compute partial functions from N to N. Also, given H, we can enumerate all effective algorithms (EA's) and thereby also all computable numbers (since these are generated by EA's), like so:

n: 0 1 3 4 5 6...

EA0 2 80 0 5 3 11

EA1 0 6 34 7 15 1

EA2 ... ... 14

EA3 ... ... ... 3
...

Each row can be seen as giving the decimal expansion of some real number r∈[0,1].

But then, of course, we can diagonalize out of this list, by taking the diagonal 2 6 14 3 and adding e.g. 1 to each term, etcetera. Thus we obtain a new computable real number (since we have just outlined an algorithmic procedure for generating it) which however is not on the list. Thus we also have a new EA not on the list. But if we had H, we should have been able to list all the EA's. But apparently we haven't. So H can't exist...

Do you think this reconstruction is basically correct? I realize that many different diagonalization proofs for the undecidability of the Halting problem are possible as well. The route through the computable numbers just seems most convenient to me, but that's probably just a subjective preference.

What can be a bit confusing about these diagonalization proofs (as opposed to the other proof strategy, where we use H to construct D=L⋅H) is that they suggest that the set of computable numbers and the set of EA's are uncountably infinite -- it is easy to fall into this mistake because diagonalization is of course also crucial to Cantor's proof of the uncountability of Pow(ℕ).

It took me some time to figure this out. But what seems to be at stake here is the difference between just countability and algorithmic countability (= recursive countability = effective enumerability). If a set S is just countable, then all that is required is that there is some bijection f:ℕ→S. But S is also algorithmically countable if f is computable (if there is an effective algorithm for f). So algorithmic countability is a stronger condition than just countability: something can be countable without being algorithmically countable.

Now what the above diagonalization argument shows is that the set of all computable numbers and the set of all EA are not algorithmically countable. We have no algorithm for listing just all EA's (and hence all computable numbers) since that would require solving the Halting problem.

But this leaves untouched the fact that those sets are 'just' countable... This countability follows from the fact that we can list all possible algorithms (so including those that compute partial functions) given the finiteness of the relevant alphabet used to construct the algorithms. And then the set of EA's is just a subset of this countable set of all algorithms. And so the subset of AE's is countable as well.

 

[Stoney Pete]

I see that I can't get my array for all possible EA's and their outputs for all inputs properly aligned... I trust you will nevertheless understand its meaning.

 

[nomadreid]

I think your real number listing would be more elegant in binary...anyway, perhaps this is of interest
https://en.wikipedia.org/wiki/Computable_number#Countable_but_not_computably_enumerable

 

[Stoney Pete]

How would you go about listing the computable real numbers in binary terms?

 

[stevendaryl]

How would you go about listing the computable real numbers in binary terms?

That's the point---the collection of all computable real numbers can't be listed.

There is probably a technical definition of computable real, but for the sake of this discussion, let's make up a definition. Let's concentrate on the real numbers in the range $0 \leq x \lt 1$. Using binary expansion, you can write every one of the reals in that range as an infinite sequence of 0s and 1s (with the slight complication that every number that is all 1s after some point can be written alternatively as a number that is all 0s after some point: the binary number 0.0111... is the same as the binary number 0.111...).

So we can define a number in this range to be computable if there is a computer program $f(n)$ that takes an arbitrary integer $n \geq 0$ and returns 0 or 1, depending on the $n$^th bit in the binary expansion.

The problem is that for $f$ to compute a real, it must be that $f(n)$ halts for every possible input $n$. According to the Halting Problem, there is no way, in general, to know which programs halt and which ones do not.

What we can do is list all partial reals in the range $0 \leq x \lt 1$. We can enumerate all functions $f$ such that:

• $f(n)$ takes an integer argument $n \geq 0$.
• If $f(n)$ halts, then it either outputs 0 or 1.
• But we don't necessarily know whether $f(n)$ halts or not.

So, let $f_1, f_2, ...$ be a list of all partial functions that take a nonnegative integer and returns 0 or 1 if they halt. Then if function $f_n$ is total (halts on all inputs), then there will be a corresponding computable real. But if doesn't halt for some input, then there is no corresponding computable real. So we have a listing that includes every possible computable real, but it doesn't include only the computable reals. A diagonalization argument shows that there can be no list that includes only the computable reals.

 

[nomadreid]

I was not indicating that putting it in binary (or anything else) would end up giving you computable enumerability (stevendaryl does a nice job of taking care of that, expanding on the reference I cited). I was just taking off from your comment that

Each row can be seen as giving the decimal expansion of some real number r∈[0,1].

There are many ways of doing this; often one simply concentrates on the computable real numbers 0 ≤ s < 1 (leaving implicit the fact that all integers are computable, and then the real number r is computable iff there is an integer k such that there exists a computable s, 0 ≤ s <1 such that r=k+s.). Then the way you do it, by having sequences of natural numbers, implicitly sets each sequence A in a 1-1 correspondence with a subset S_A of natural numbers, which in its turn is usually put in correspondence with a real number r by specifying that the expansion in base b of r equals Σ_n∈SAb^-(n+1) . You can of course use b=10, or base 2, or whatever is your choice. I just like 2 because then one can equal the answer to the question "is the number c in S_A? Say 0 for no and 1 for yes" equal to the number in the n+1'st place. I didn't say it was necessary, just maybe more elegant, even if it wouldn't lead anywhere (after all, Sir Francis Drake finished the rubber as the Spanish Armada was attacking). Anyway, elegance is a matter of taste.

 

[Max Rowell]

Alright, so maybe you can't say if a program will start or stop. What if a program could detect under what conditions any program will start or stop? Is that possible?

 

[nomadreid]

Either "no" or "please make that more precise". You could of course give some conditions upon which you would know whether it starts or stops, but what you are asking is either vague or simply robbing Peter to pay Paul. A program P that could detect under what conditions any program Q will start or stop -- we must ask what the input and output into such a super-program would be? Assuming the input is a program, then I presume the output, the "conditions", would be a set of data S for the program under which it will stop. In this case, if a program P could do that, then you could build another program Q that , given a random program R and data D, would just run R through P and then check whether D was a member of S, thereby violating the undecidability of the halting problem. Or perhaps you meant something else?

 

[SSequence]

The statement of the problem is not difficult to describe precisely.

Statement S1
The function h:ℕ²→ℕ defined by equation:
h(x,y)=1 --- φ_x(y) is defined
h(x,y)=0 --- φ_x(y) is undefined
is not a (total) computable function.

φ_x(y) means the result/output that a program with index x gives when given the input y. The term φ_x(y) can also be undefined, if the program doesn't halt for the given input.

Statement S2
The function f:ℕ→ℕ defined by equation:
f(x)=h(x,x)
is not a (total) computable function.

==========================

That's all there is to it, more or less. There are just few points to note here:
(1) The statement S2 implies the statement S1. To prove this note that S2→S1 is equivalent to proving:
~S1 → ~S2
which is easy to prove.

(2) The proof of statement S2 uses the fact that the function "h" in statement S1, and hence the function "f" in statement S2 must be total. What is shown is essentially is that every program (with say an index i) that computes a total computable function (of one variable) will differ from the function "f" on at least one value (obviously it follows trivially that the difference will be on an infinite number of values).

Then from S2 being true we can infer S1 (due to the implication S2→S1).

Edit:
Just so that it is clear, the function g:ℕ→ℕ defined by equation:
g(x)=h(x,0)
is also not a (total) computable function (by very similar reasoning to one given in (2) above).

 

[Max Rowell]

Either "no" or "please make that more precise". You could of course give some conditions upon which you would know whether it starts or stops, but what you are asking is either vague or simply robbing Peter to pay Paul. A program P that could detect under what conditions any program Q will start or stop -- we must ask what the input and output into such a super-program would be? Assuming the input is a program, then I presume the output, the "conditions", would be a set of data S for the program under which it will stop. In this case, if a program P could do that, then you could build another program Q that , given a random program R and data D, would just run R through P and then check whether D was a member of S, thereby violating the undecidability of the halting problem. Or perhaps you meant something else?

Well I was thinking, what if instead of deciding start or stop, you assumed it was a program that was undecidable by default. The big obstacle in halting problem is the Liar's Paradox Program, where if I say it will stop it will continue to run, while if I say it will run it will stop. But what if I say "This program will stop should I attempt to say it goes, and it will go should I want to say it stops". This should also resolve programs run on atmospheric noise. What do you think?

 

[SSequence]

I also noticed something else while writing post#13. In some sense, it seems to me, it highlights a certain difference between a "machine" based model and a "program" based model. If we enumerate all TMs (turing-post machines) so that for each element of ℕ, we assign a unique TM to it, then it seems that the same machine can be thought of as:
-- computing a total function of one variable
can also be thought of as:
-- computing an entirely different partial (or total) function of two variables (just as example) etc. etc.
-- computing an entirely different partial (or total) function of three variables etc.

That's because the same program (defined by states/actions) will act differently based on what the initial contents of the tape are. So, to the same program (and hence to same index), we are assigning functions of different arity (with a single function assigned to a given arity).

On the other hand, if we use some kind of "program" model, where we have some sort of input variables, it seems more natural to assign to each index a "single" function of a "fixed" arity.

But ofc there is no compulsion in any of this. With some changes (in our enumeration) we can flip the characteristic specified for both cases.
At any rate, none of this really seems to affect any of the proofs above though. But I do not know whether such differences in enumeration can be (potentially) substantial in some cases perhaps.

(Moved from post#13)

 

[stevendaryl]

Well I was thinking, what if instead of deciding start or stop, you assumed it was a program that was undecidable by default. The big obstacle in halting problem is the Liar's Paradox Program, where if I say it will stop it will continue to run, while if I say it will run it will stop. But what if I say "This program will stop should I attempt to say it goes, and it will go should I want to say it stops". This should also resolve programs run on atmospheric noise. What do you think?

I'm not sure I understand what you're saying. Yes, you can think of the proof of the halting problem as setting up something analogous to the Liar Paradox. But what are you hoping to do with this analogy?

What I'm guessing you might be thinking is that maybe you can classify things into three categories: (I will use the word "computation" to mean a program run on a specific input)

1. Computations that definitely halt.
2. Computations that definitely do not halt.
3. Computations that are paradoxical (so that there is no way to know).

If that's your idea, it really doesn't work. The proof of the undecidability of the halting problem doesn't actually establish the existence of some paradoxical program. Instead it shows that the assumption that there is a particular program (one that gives yes or no as to whether a computation halts) leads to a contradiction. If an assumption leads to a contradiction, that means that the assumption is false. So there is no such program.

What you could do is come up with a three-valued program: $H(x,y)$ which returns "True" or "?" if program number $x$ halts on input $y$, and returns "False" or "?" otherwise. So an output of "?" would mean "Don't know what the answer is". Some terminology:

• $H$ is "unsound" if $H(x,y) =$ "False", but program $x$ really does halt on input $y$, or if $H(x,y) =$ "True", but program $x$ does not actually halt on input $y$.
• If $H_1$ and $H_2$ are both sound, then we can say that $H_1 \geq H_2$ if for every $(x,y)$, either $H_1(x,y) = H_2(x,y)$ or $H_2(x,y) =$ "?" (In other words, either they both give the same answer, or $H_1$ gives a definite answer (True or False) while $H_2$ gives an uncertain answer ("?")
• We say that $H_1 > H_2$ if they are both sound, but there is at least one pair $(x,y)$ such that $H_1(x,y)$ is definite, but $H_2(x,y)$ is "?"

Another way to state the unsolvability of the halting problem is that given any sound 3-valued program $H$, we can find another program $H'$ such that $H' > H$. So there is no best such program.

 

[SSequence]

What you could do is come up with a three-valued program: $H(x,y)$ which returns "True" or "?" if program number $x$ halts on input $y$, and returns "False" or "?" otherwise. So an output of "?" would mean "Don't know what the answer is".
...
Another way to state the unsolvability of the halting problem is that given any sound 3-valued program $H$, we can find another program $H'$ such that $H' > H$. So there is no best such program.

I think that a setup of similar kind (perhaps with some changes in meaning) might be necessary if one is not comfortable with using two-valued/classical logic (in the given domain). In fact, I re-call being dissatisfied after reading (and understanding) the standard proof the first time (in context of natural nos.).

Also:

What I'm guessing you might be thinking is that maybe you can classify things into three categories: (I will use the word "computation" to mean a program run on a specific input)

1. Computations that definitely halt.
2. Computations that definitely do not halt.
3. Computations that are paradoxical (so that there is no way to know).

If that's your idea, it really doesn't work. The proof of the undecidability of the halting problem doesn't actually establish the existence of some paradoxical program.

I take (3) to mean "loops (infinite computations) whose existence (as infinite) is absolutely unprovable". I am more inclined to think that such computations don't exist, but I feel there is a lot of burden in both directions (showing the existence or non-existence of such loops). Ofc there is a long history behind this (originating from intuitionism).

The people who believe in non-existence of (3) might perhaps assert that at least one explicit example of existence of such loops should be proven. My feeling is that:
-- either such loops, as in (3), don't exist
-- or such an explicit example of (3) exists but simply can't be proved (in any "reasonable" sense) ... even for a single instance

For the last possibility, I would love to see an explicit example or instance that could be "proved" somehow, but I just don't know how one would even start (nor I am aware of anyone at all trying to do it ... I honestly think perhaps rightly so). But maybe there is a way? At least I am simply completely unable to see how would one even begin thinking about it.

Perhaps one might imagine some kind of point where it just becomes extremely difficult to see how to increase the bb strength (which you defined in a recent thread) of a theory beyond a certain point (even in principle) ... without resorting to completely unwarranted conjecturing. So, even people who might believe in non-existence of (3) might start to think over their conviction. At any rate, this would be nothing like a proof (and hence such doubt in conviction might not be well-founded). And I am really just thinking of it as a hypothetical scenario.

The people who believe** in existence (of loops like (3)) might perhaps assert that a proof of non-existence of (3) should be given. Some people believe that a proof of non-existence of (3) can't be given because of Church's thesis. But I consider the underlying matter to be more subtle though. There seem to be possibly concrete questions*** that might (for all practical purposes) possibly lead to "impossibility of proof of non-existence of (3)" ... but I certainly don't think the reason is Church's thesis(at least seen in its usually interpreted way with bounded memory), even if the conclusion turns out to be the same .** One might also believe that one of the following possibilities must be true (without being definitive about which one):
(i) loops like (3) do not exist
(ii) loops like (3) exist

*** The full detail of this perhaps might be off-topic, so I will leave it. In case some is interested, I will mention the precise question.