Talk:Turing's proof
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics rating: | B Class | Low Priority | Field: Foundations, logic, and set theory | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
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!
