0
$\begingroup$

This is something that has bugged me for a while, so I hope you can help me.

Suppose:

  • $A'$ is the set of all programs,
  • $halt?$ is the halting problem solver,
  • $D$ is the program that is constructed in the proof to show HP is undecidable

Obviously $halt? \in A'$ and $D \in A'$.

$A' - halt? = A$ is the set of all programs except $halt?$ and all programs that uses $halt?$ e.g $D \notin A$.

So it seems to me that what Turing's proof shows is that HP is undecidable for the set $A'$. It does not show that it's undecidable for the set $A$.

It also seems that every valid program that ever written is in $A$

Did I misunderstand something? If not is there any $halt?$ program to decide $A$ or $A$ is also undecidable?

Edit

I think, I didn't say correctly what I meant. and I know that I misused the $X - y$ notation but I hoped you get what I mean.

Suppose:

  • $A'$ is the set of all programs,
  • $halt?$ is the halting problem solver that may produce the wrong answer
  • $D$ is the program that is constructed in the proof of HP and instead use my version of $halt?$
  • $A = A' - \text{{D}}$
  • $The\ Halt?$ is the original halt? program in the proof of HP

by the same arguments of proof of HP we can prove that $halt?$ give the wrong answer for $D$. so we proved that $halt?$ surely not working correctly for at least one program $D$

we now know that $The\ Halt?$ program doesn't exist so $D$ program doesn't compile. so let's exclude it from the set of all possible program

now the question is this: Is the set $A$ is decidable?

My understanding is that The HP proof does not say anything about A.

$\endgroup$
  • $\begingroup$ In response to your edit, again, the program $D$ doesn't exist. So excluding it does nothing. You are misunderstanding the proof of the halting problem as I explain in my answer. $\endgroup$ – 6005 Apr 12 '17 at 20:20
5
$\begingroup$

The following was written before the extensive edit to the question, but the edit doesn't really change anything. The point remains that the proof shows that no program decides the halting problem, so it shows that the set "$A'$ minus some programs that don't exist" is just $A'\setminus\emptyset=A'$.

Obviously $halt?\in A'$ and $D\in A'$.

That's not obvious. Indeed, the point of the proof is that it's not even true. Turing proves that $halt?\notin A'$ – there is no Turing machine (program) that decides the halting problem.

$A' - halt? = A$ is the set of all programs except $halt?$ and all programs that uses $halt?$ e.g $D \notin A$.

If $X$ and $Y$ are sets, then $X-Y = \{e\mid e\in X\text{ but }e\notin Y\}$. Where $y$ is an element, people sometimes write $X-y$ as shorthand for $X-\{y\}$.

Let us assume, for a moment, that $halt?$ is a program. Then $A'-halt?$ would be the set of all programs except for $halt?$. In particular, if $halt?$ were a program, then $D$ would be a program and, contrary to your claim, $D$ would be in $A'-halt?$. As it is, neither $halt?$ nor $D$ is a program, so $A'=A$.

If not is there any $halt?$ program to decide $A$ or $A$ is also undecidable?

$A$ is just the set of all programs. It is decidable, just like the set of all Java programs is decidable. Do you mean to ask if the halting problem for $A$ is decidable? If so, it is the very thing that Turing has proven to be undecidable, since $A=A'$.

$\endgroup$
1
$\begingroup$

There's a few pieces here.

First, your proof regarding $A$ is correct: it is possible to construct a set of programs for which $halt?$ can correctly determine whether they halt or not. That has never been the issue. Everyone knows that there are programs for which we can determine whether they will halt.

It also seems that every valid program that ever written is in $A$

This one is trickier. Your claim sounds like it should be obvious, but without having named $halt?$ it's not really reasonable to determine whether any program does not contain this unspecified $halt?$.

In fact, one real issue you run into is that real computers are not actually Turing machines because they lack the mythical "infinite tape" that is required for a Turing machine. Real computers are finite automata. And it is easy to prove whether a finite automata terminates or loops in finite time (the proof is trivial, in fact). By that logic, we can comfortably say that we have never written a program that is not decidable.

Even here, though, there's some value in realizing that it could be "hard" to determine if a program halts or not. Consider this one, in pseudocode:

loop over every permutation of a 160 byte string
    calculate the SHA-1 hash of this string
    if the hash is equal to 0000000000000: terminate

Determining whether this program terminates could potentially require more energy than exists in our galaxy! That's pretty darn close to undecidable! In fact, it is not currently known whether there is a 160 byte string which hashes via SHA-1 to be all 0s. It is theorized that it should be likely to be true, but that's as far as our mathematicians have gotten!

So the real world practicality of decidability is still there. The interesting part about decidability in the Turing complete land is that, even given access to some infinite resources, there are still some undecidable problems.

$\endgroup$
  • $\begingroup$ I like your answer. do you agree that in HP's proof we actually have to assumption $\endgroup$ – raoof Apr 13 '17 at 5:49
  • $\begingroup$ what do you mean by "we actually have to assumption?" $\endgroup$ – Cort Ammon Apr 13 '17 at 5:52
  • $\begingroup$ sorry I made a mistake. do you agree that in HP's proof we actually have two assumption: first there is a $halt?$ program, second it works correctly for all program, and it proves that our second assumption is false by giving an example program $D$ ? because others do not @DavidRicherby $\endgroup$ – raoof Apr 13 '17 at 6:01
  • $\begingroup$ I have to be careful with the wording here, because we are doing a proof by contradiction. The proof goes that if a program halt? existed which we assumed solved the halting program for all inputs, then we can identify a contradiction (the example program D) which demonstrates that the assumption was false. So in that sense, you could say we assumed that the halt? program existed, but in actuality, we only assumed it in order to prove that that assumption is always invalid and that the halting problem is, in fact, undecidable. $\endgroup$ – Cort Ammon Apr 13 '17 at 6:06
  • $\begingroup$ yes if you count $D$ but if you don't count $D$ it still an open question, isn't it? $\endgroup$ – raoof Apr 13 '17 at 6:16
1
$\begingroup$

The halting program, $halt?$, does not exist, and neither does $D$. In reality, then, your $A'$ and your $A$ are identical. The halting problem cannot be solved for either of them.

However, on second thought, your question is not completely bogus -- if I think about what you really meant to say. In the proof that the halting problem is undecidable, instead of assuming that $halt?$ exists and deriving a contradiction, you can think of it as taking any program $H$, and showing that $H$ does not solve the halting problem. Specifically, imagine $H$ solves the halting problem for many inputs, but perhaps it doesn't work on every input (either it returns the wrong answer, or maybe it doesn't halt at all). Then what does the proof tell us about $H$?

First, the proof constructs $D$, which on input $x$ runs $H$ on $(x,x)$; then, if $H$ says it halts $D$ runs forever and if $H$ says not, $D$ halts. Then we consider $D$ on input $D$. IF $H$ can deduce the correct behavior of $D$ on input $D$, then we get a contradiction: if $D$ halts, $D$ actually runs forever, and if $D$ doesn't halt, $D$ actually halts. That is, IF $H$ answers correctly on input $(D,D)$, we get a contradiction.

Therefore, we have shown that $H$ cannot decide the answer correctly on input $(D,D)$. But this doesn't mean that there can't be a smaller set of programs on which $H$ correctly decides the answer. Indeed, many practical algorithms exist for deciding whether some programs halt (usually simple ones).

by the same arguments of proof of HP we can prove that $halt?$ give the wrong answer for $D$. so we proved that $halt?$ surely not working correctly for at least one program $D$

Yes, exactly -- we proved $H$ doesn't work for $D$ on input $D$, but maybe $H$ works for other programs.

we now know that $The\ Halt?$ program doesn't exist so $D$ program doesn't compile. so let's exclude it from the set of all possible program

Be careful how you word things -- you can't exclude a program that doesn't exist. But, I'm thinking what you meant to say is, rather than excluding the non-existent program $halt?$, exclude the program $H$ which only sometimes solves the halting problem. Then, sure -- you can absolutely do that.

now the question is this: Is the set $A$ is decidable?

My understanding is that The HP proof does not say anything about A.

You are right that we haven't proved that the halting problem on $A$ is not decidable!

However: no, $A$ is not decidable. For starters, there are an infinite number of programs that behave exactly like $D$, but aren't equal to $D$ (for instance, they have a bunch of extra lines of code that do nothing). You'd have to exclude those as well -- even writing down a list of programs equivalent to $D$ is not a decidable problem, not something you can do easily.

Computer scientists have tried very hard to find a subclass of programs for which the halting problem is decidable, and many such classes exist -- for example, the class of loop-free programs. But it is not enough just to exclude $D$ and $H$. In fact, you will likely have to exclude most programs. You will never succeed in solving the halting problem just by disallowing some specific small number of programs.

$\endgroup$
  • $\begingroup$ if we assume that there is $halt?$ program that works correctly for almost all but not every program then $D$ does exist. can't we interpret HP's proof as a proof of existence of program that $halt?$ give the wrong answer? $\endgroup$ – raoof Apr 13 '17 at 5:20
  • $\begingroup$ @raoof Aha -- now I understand what you're saying! I am sorry I didn't understand it before. Now I have updated my answer; it is a bit long but I hope readable. Does this answer your question? $\endgroup$ – 6005 Apr 13 '17 at 22:03

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.