2
$\begingroup$

Posted this question on cstheory.SE where they said to go here:

I read the demonstration of the Halting problem, it is done by reductio ad absurdum where the push to get to the absurd is to use the halting function "H(A,b)" (where A=another function, b=the A parameter) as its own parameter. This proofs that can't exist a function which takes every function including its own as parameter and says if it is an infinite loop or not, but doesn't proof that a function Z(A,b) where {A,b!=Z} (1*) can't exist.

While I deleted that question I had this answer by dkuper:

It is easy to circumvent this problem, by giving to the functions the code of a different machine which computes the same function.

Say you succeeded in building your machine computing Z(a,b) which works as you said. Then you still get the reductio ad absurdum, by feeding to this machine the code of another machine which is equivalent. This is always possible because for every machine M, there are infinitely machines M′ which behaves the same as M (i.e. halt on exactly the same instances). So checking that the input is not precisely the machine M is not enough to avoid the paradox. And checking that the input does not behave the same as M is impossible.

So, now, this doesn't work if we assume that the function passed as parameter has a flag (applied by the constructor) that indicates if it is the halt function.

$\endgroup$
  • $\begingroup$ Interesting question, will be intrigued to see how it's answered. My hunch: by passing a flag identifying some arbitrary TM as equivalent to the halting function, you're basically admitting your TM access to an oracle. This oracle allows your TM to solve the halting problem. In general, determining whether a TM computes the same function as your TM (i.e., the halting function) is not computable... unless you have a TM to do it :) $\endgroup$ – Patrick87 Jan 9 '14 at 17:43
  • $\begingroup$ @Patrick87 The flag is applied by the constructor of the TM $\endgroup$ – user12708 Jan 9 '14 at 17:47
  • $\begingroup$ Not sure whether you mean that should invalidate my point; I don't think it does. Passing a flag as you suggest is similar to passing an answer (albeit partial, in this case) along with the input. Unless the constructor of the original TM has some mechanical means of ensuring that his TM computes the halting function, how does he know what to set the flag to? He's an oracle for the purposes of discussion. $\endgroup$ – Patrick87 Jan 9 '14 at 17:56
  • 1
    $\begingroup$ So, he constructs a TM. How does he know what function it computes? $\endgroup$ – Patrick87 Jan 9 '14 at 19:34
  • 4
    $\begingroup$ Oh dear, this is a case of "it's not even wrong", I'm afraid. What you want to do does not make a lot of sense; hardcoding special cases won't solve a problem that has the powers of infinity behind it. See my answer. $\endgroup$ – Raphael Jan 9 '14 at 23:25
6
$\begingroup$

Let's do this step by step.

  1. "Z(A,b) where {A,b!=Z}"

    I understand this to mean "just forbid input Z for algorithm Z". You can not do that. A machine that is supposed to solve the halting problem has to work on all machines, by definition of the problem. In other words, you make the assumption "Let Z be a machine that does not solve the Halting problem" -- that does not lead anywhere.

  2. dkuper's argument is correct: you can derive the contradiction by feeding any of the infinitely many indices of the (assumed) solver of the halting problem, arriving at the same contradiction. Since this set of indices is not recursive, you can not program your machine to detect every alias.

  3. Then the machine does not solve the halting problem anymore (see 1). Even if we had some leeway there, just assume the function that solves the halting problem for all functions but the one which solves the halting problem, and do the same proof.

    And when you try to fix this in the same way, I'll get another function. And another one. There are enough of them.

In other words, your strategy of fixing one (or finitely many) special cases won't lead you anywhere. The halting problem is far too undecidable for that -- as the proof shows.

$\endgroup$
  • $\begingroup$ my words could be wrong, but we are the experimental proof that an halting machine can be built in some way $\endgroup$ – user12708 Jan 10 '14 at 8:00
  • 2
    $\begingroup$ @user2993157: No, not at all. Have you built one? Or are you suggesting we are the machine; oh, no, human minds are so easy to fool. (It's a bit silly to say "this mathematically sound proof is wrong because I can special-case it into the distance!". It's like saying "clearly mass repels mass; look, I can throw a ball in the sky!".) Note, furthermore, that the proof makes no assumptions on how the machine is constructed. If you were able to build one by corraling all TCSists, the contradiction by self-reference would still arrive. $\endgroup$ – Raphael Jan 10 '14 at 9:14
  • $\begingroup$ Can you proof that an algorithm halts or don't halts? Can take 1 bilion years for you, but theoretically it can ever be done. $\endgroup$ – user12708 Jan 10 '14 at 9:39
  • 2
    $\begingroup$ @user2993157: I can prove it for some, but surely not for all of them. And no, it can not be done theoretically, since there is a theoretical proof it can not. In any case, the Halting problem does not say anything about humans but about machines. Since humans can never form a Turing machine (they don't have arbitrarily much time and resources), the point is moot. I don't think this discussion is fruitful. You seem to be convinced your (wrong) intuition outweighs a mathematical proof and I won't agree with that. $\endgroup$ – Raphael Jan 10 '14 at 9:57
  • 1
    $\begingroup$ @user12708 The thing is, "Can you decide that a specific program halts?" isn't the Halting Problem. It's "Can you decide whether any program halts using the same algorithm?" If you give me some small program I can probably come up with a proof that it halts or doesn't, and I can come up with some simple algorithms that work on some programs. E.g. If the first instruction in the program is to give an answer, clearly the program halts. But that won't work on all programs, and there is no one algorithm that does. $\endgroup$ – Doval Feb 17 '15 at 17:11

Your Answer

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