0
$\begingroup$

I know there's like a thousand questions about this topic in the site and elsewhere. I'm just going to pick one that at least for me it serves as a good basis for my question. The answer by Rick Decker is the one that I understood more, so I'm just going to take it as a basis for my actual doubt.

It's not difficult to see that if one adds an if (and extra loop) into 'Halting Program ' $H$, then feeding $H$ to itself yields a contradiction. What it confuses me is why to add the extra loop to force the contradiction, if by hypothesis $H$ solves (itself?)

It doesn't seem logical to say first (of course I'm missing something), hey I give you $H$ that solves your issue, but afterwards I give you an augmented $H$ that does not and so we reach a contradiction.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

What we show is that this augmented $H$ can not even exist. You gave me $H$, and I gave you back an augmented $H$, called $\hat H$. We can build this $\hat H$ by adding the extra loop and if statement, but its easy to show that this augmented $\hat H$ will never be able to exist: $\hat H(\langle \hat H\rangle)$ is not either rejecting or accepting, nor stuck in an infinite loop, but we know that any TM must be either one of those.

Therefore, we get a contradiction to the existence of $H$: we showed that if $H$ exists, then some other $\hat H$ exists, but also $\hat H$ couldn't ever exist.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the explanation of the ancillary $\hat{H}$ that it is what actually does the job. Do you know if it's there a possibility to show this without contradiction? $\endgroup$
    – user2820579
    May 11, 2021 at 13:46
  • 1
    $\begingroup$ Not that I know of. But there is a way (without proving by contradiction) to show the existence of undecidable languages (and not proving specifically that the halting problem is such a language) $\endgroup$
    – nir shahar
    May 11, 2021 at 13:47
  • $\begingroup$ I guess this is standard in CS, got any ref where this is treated? $\endgroup$
    – user2820579
    May 11, 2021 at 13:49
  • 1
    $\begingroup$ Try to prove using a counting argument: How many TMs are there? (hint, we can write down the code of a TM, how does this help us bound the number of TMs?) And how many languages are there? You will see there are significantly more languages than TMs, hence the existence of undecidable languages (and even unrecognizable languages) $\endgroup$
    – nir shahar
    May 11, 2021 at 14:39

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.