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.

Improve this question
$\endgroup$
11
  • $\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, 2014 at 17:43
  • $\begingroup$ @Patrick87 The flag is applied by the constructor of the TM $\endgroup$
    – user12708
    Jan 9, 2014 at 17:47
  • 1
    $\begingroup$ So, he constructs a TM. How does he know what function it computes? $\endgroup$
    – Patrick87
    Jan 9, 2014 at 19:34
  • 5
    $\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, 2014 at 23:25
  • 1
    $\begingroup$ I explain it carefully at math.andrej.com/2010/03/29/… where I also address your argument and explain that it is invalid because it presupposes reductio at absurdum when it tries to derive it. This is one of those black holes of knowledge in math community. Because of it people hold such false opinions as "the proof of nonexistence of halting oracle is nonconstructive because it uses proof by contradiction". $\endgroup$
    – Andrej Bauer
    Jan 11, 2014 at 12:32

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
8
  • $\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, 2014 at 8:00
  • 3
    $\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, 2014 at 9:14
  • 3
    $\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, 2014 at 9:57
  • 1
    $\begingroup$ @user12708 You know the proof; work on understanding and accepting it, maybe by checking out other proofs by contradiction. There is no (finite) chain of intuitive arguments that disproves "solves Halting" for every single TM. $\endgroup$
    – Raphael ♦
    Jan 11, 2014 at 10:10
  • 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, 2015 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.