It is known that there does not exists an oracle $H$ which given any pair $(M,I)$ where $M$ is a machine and $I$ is an input (possibly still a machine) to have $H(M(I)) = YES$ if $M(I)$ halts and $H(M(I)) = NO$ if $M(I)$ does not halt. This was proven by Turing. However, this can be shortly written as $$ \not\exists H \hspace{0.5cm} \forall M,I \hspace{0.5cm} H(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I) \text{ halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$

But is it possible to have the following: $$ \forall M,I \hspace{0.5cm} \exists H_{M,I} \hspace{0.5cm} H_{M,I}(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I) \text{ halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$

  • $\begingroup$ This is trivially true. The machine $H_{M,I}$ doesn't even have to consider its input. $\endgroup$ – Yuval Filmus Nov 4 '20 at 8:43
  • 1
    $\begingroup$ An oracle usually signifies an arbitrary function. What Turing rules out is a computable oracle $H$. $\endgroup$ – Yuval Filmus Nov 4 '20 at 8:44

Yes. Given a machine $M$ and input $I$, one of the two things happens:

  1. $M(I)$ halts.
  2. $M(I)$ does not halt.

We may not be able to predict or compute which of these happens, but one and only one happens simply by rules of classical logic.

Now to show that $H_{M,I}$ exists we consider two cases:

  1. If $M(I)$ halts then $H_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "yes".
  2. If $M(I)$ does not halt then $H_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "no".

Note: we proved existence of $H_{M,I}$, but we did not give a way of computing $H_{M,I}$ from $M$ and $I$, which is impossible as that would give us the halting oracle (exercise).

So, what Yuval said.

  • $\begingroup$ Well, I thought it is implicitly understood (from the definition of $H_{M,I}$) that $H_{M,I}$ should always halt ... $\endgroup$ – C Marius Nov 4 '20 at 9:27
  • $\begingroup$ You have to halt to output something, aren't you ? $\endgroup$ – C Marius Nov 4 '20 at 9:28
  • $\begingroup$ Oops, fixed it. $\endgroup$ – Andrej Bauer Nov 4 '20 at 9:50
  • $\begingroup$ Thank you for your time! But, I do not know how being able to compute it, for the particular case $M,I$, would give the halting oracle (which is for all $M,I$)! Can you hint me in the direction? $\endgroup$ – C Marius Nov 4 '20 at 9:54
  • 2
    $\begingroup$ No, I am not going to hint you in the right direction only 30 minutes after I posted my answer. You should get used to thinking about a problem longer than that. If after two days of thinking you don't see the answer, then I think it would be appropriate to get a hint. You really need to try yourself and be persistent. $\endgroup$ – Andrej Bauer Nov 4 '20 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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