I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) . I’m having some difficulty understanding the argument as it is made. Let me explain it as I see it:

So that our terminology is the same, H is a (hypothetical) program which can analyze another program to see if it halts. H+ is a modified version of H which loops forever if the analyzed program halts and halts if the analyzed program does loops forever.

In order to run H, you need to specify 2 things – a program and the input to that program. The Input to the analyzed program is necessary because the program’s behavior will depend on its input.

According to Computerphile’s explanation of Turing’s argument, we are asked to consider what would happen if H+ were to analyze H+ with H+ as its input. Since there are a lot of H+’s being thrown around, let’s define H+1 as the program that I am running, H+2 as the program being analyzed, and H+3 as the input to H+2. (Of course, H+1, H+2, and H+3 have the exact same code; they are just being used in different ways.) My question is this: if we require H+3 as an input to H+2, then shouldn’t we require an input to H+3? And if we continue the pattern and use H+4 as an input to H+3, then wouldn’t this mean that we require an H+5 as an input to H+4? And so on?

If you counter by saying that Turing’s argument doesn’t require H+3 to have an input (or that its input doesn’t have to be H+), then doesn’t this break the whole symmetry of the problem? After all, the whole point of Turing’s argument (as I currently understand it) is that if H+2 runs on H+3 and halts then it would be a contradiction to have H+1 loop forever on H+2 since H+1,H+2,and H+3 are all identical (and vice versa were H+2 to loop forever on H+3). But the situation isn’t identical. In one case H+2 is running on H+3. In the other, H+1 is running on "H+2-running-on-H+3".

I guess you could say that each H+ maybe can only look one step in front of it, so that H+1 only “sees” H+2 and H+2 only sees H+3. But then what does H+3 see? Doesn’t it need some input of its own? After all, whether or not H+3 halts depends on the program it’s given. If so, this brings it back to my first point (that we would need an H+4).

It seems to me this whole argument falls apart. Either you would need an infinite stack of H+’s which can’t happen, or you have a finite stack which because of the discontinuity at the end means that the symmetry of each level doesn’t translate to the one below it.

So what am I missing?


"So what am I missing?" ​ Nothing. ​ ​ ​ Computerphile should have defined H++ by ​ H++(x) = H+(x,x) , ​ and then run H++ on itself.

  • $\begingroup$ Can you please clarify this? I am unfamiliar with this notation. Is x the input? And if it is, then doesn't the problem still exist? Putting H++<sub>2</sub>(x<sub>2</sub>) into H++<sub>1</sub>(x<sub>1</sub>) gives you H++<sub>1</sub>(H++<sub>2</sub>(x<sub>2</sub>). So what do you use for x<sub>2</sub>? $\endgroup$ – Israel Aug 26 '16 at 16:34
  • $\begingroup$ It's just function notation. ​ Yes. ​ What are H++$_2$ and x$_2$ and H++$_1$ and x$_1$? ​ ​ ​ ​ $\endgroup$ – user12859 Aug 26 '16 at 16:46
  • $\begingroup$ I am using the subscripts to keep track of which H++ I am referring to (I was doing something similar in my original question). H++₁(x₁) is the program I am running and x₁ is the input into that program. H++₂(x₂) is the program that I am going to be inserting into H++₁. In other words: x₁=H++₂(x₂) so we have H++₁(x₁) = H++₁(H++₂(x₂)). So then, why don't I need to specify x₂? $\endgroup$ – Israel Aug 26 '16 at 21:22
  • $\begingroup$ Well, H++$_2$ itself is the program that you should be inserting into H++$_1$. ​ In other words: $\hspace{1.006 in}$ x$_1$=H++$_2$≠H++$_2$(x$_2$) so we have H++$_1$(x$_1$) = H++$_1$(H++$_2$) ≠ H++$_1$(H++$_2$). ​ So then, you don't need to specify x$_2$ because no such thing is involved in the input to H++$_1$. ​ ​ ​ ​ $\endgroup$ – user12859 Aug 27 '16 at 16:17

The problem is just the number of inputs of the program H+. Let's try to rewrite it:

H takes an input d and and input i.
For simplicity, let's say that H+ only takes one input x and calls H with the inputs x and x, i.e, the same input twice.
(You can think of H+ as a program taking two inputs and discarding the second one, just uses the first and passes it to H, twice)

If H exists, H+ exists.

If H+ halts on input H+, then H+ does not halt.
If H+ runs forever on input H+, then H+ does not run forever.

Conclusion, H does not exists.

You can read this also: http://www.jjinux.com/2010/05/python-halting-problem.html


I wonder if it will be easier to understand the real issue if there is a sly version of the Halts(program,input) program that instead was HaltsInUnderTenOperations(x,i).

Maybe you can use the same argument against Halts(x,i) to prove HaltsInUnderTenOperations(x,i) is not possible either, if you feed it to a program that halts it if it says no (would have taken ten or more operations) but makes it take ten or more operations if it says yes (would have halted in under ten operations).

Or rather than ten, choose an appropriately small finite number for which it would be self-evident that you can easily tell what the output of HaltsInUnderTenOperations will be - in other words, you can solve it but it is a logical contradiction and therefore an impossible program.

The fact there is nothing wrong with the program that halts or doesn't based on the simple "yes/no" input, means the program that has something wrong with it is the Halts (or the HaltsInUnderTenOperations).

This may seem confusing but it is similar to how the Busy Beaver problem is easily solvable from 1 or 2 states.

  • $\begingroup$ This doesn't work at all. HaltsInUnderTenOperations (assuming it means what it sounds like it means) is easily decidable: you just simulate the machine and, if it halts within ten steps, you say "yes" and if it doesn't, you say "no". Your contradiction fails because there's no guarantee that you can determine whether a machine halts within ten steps, and then do further processing, all within ten steps. And what's wrong with "getting into a definition of 'computable'"? Isn't that the whole point? $\endgroup$ – David Richerby Mar 19 '19 at 15:12
  • $\begingroup$ I have made it more clear, and my original post may even be against the rules because it said something vaguely like "don't post if you don't know what you're talking about", which is probably the case with me in that post. Could you perhaps enlighten me as to a definition of computable, or discuss it, in words? Because even experts simply wave it off as meaning "the ability to solve a problem in an effective manner" and it really does seem like it's something with blurred lines. Only that if it can be solved (even easily) but not with any "tricks" then it should be considered "non computable" $\endgroup$ – lmnyx Mar 24 '19 at 15:16
  • $\begingroup$ I should also add that in Numberphile where they are solving a^3 + b^3 + c^3 = 33 etc, they say it officially "could be undecideable" (which is how this relates to the original post) and yet they are finding solutions left and right. Maybe they mean that there might be no "formula" for finding the solutions, even though enough brute force will find the solutions. Maybe I'm answering my own question here, actually. It's not like I can't learn - I even disagree with my original post but it has to stay there and affect me negatively for posting it due to the forum rules, I think. $\endgroup$ – lmnyx Mar 24 '19 at 15:24
  • $\begingroup$ @lmnyx You're welcome to delete your post at any time, which will restore any reputation you lost to downvotes. "What makes a function computable?" is actually a very good question that you're free to ask as a standalone question! But short version, it means it can be computed by a Turing machine, or a lambda-calculus expression, or a human following an algorithm: nobody's ever found something one of those models can do that the others can't. $\endgroup$ – Draconis Mar 24 '19 at 15:31
  • $\begingroup$ I also have to add another comment here for clarity. First, I cannot edit my first comment (again due to the forum) and I meant to say "my so-called answer" instead of "my original post" in that. But I do mean "the original post" in the next comment. Second, the reason I disagree with my so-called answer is because defining a finite limit to the formula probably does stop it from being analogous to the "Halts(x,i)" program. Though it would be interesting to make one to test it for real (which I'm not going to do because I'm not at that level at the moment). $\endgroup$ – lmnyx Mar 24 '19 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.