Talk:Turing's proof

From Wikipedia, the free encyclopedia

Problems with the first proof:

Suppose I switch D with a simple machine that always outputs "s". In such a case, H would loop when reaching K anyway. Doesn't it kind of makes the H machine fail by itself, making the need of D for it to fail irrelevant? And wouldn't it invalidate the proof about the existence of D? I don't mean to say that the Halting Problem isn't undecidable, but just that Turing's original proof is flawed. Or am I missing an important point here?

I've got it! The point is that D cannot output correctly its analysis of H. If D decides that H is circle-free, H becomes circular. And if D decides that H is circular, H becomes circle-free, since it wouldn't have to enter that whole circular calculation of itself. Therefore, D cannot be always right!