Trying to break the proof of undecidability of the halting problem 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.
Let's do this step by step.

&quot;Z(A,b) where {A,b!=Z}&quot;
I understand this to mean &quot;just forbid input Z for algorithm Z&quot;. 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 &quot;Let Z be a machine that does not solve the Halting problem&quot; -- that does not lead anywhere.

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.

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.