1
$\begingroup$

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}$$

Improve this question
$\endgroup$
2
  • $\begingroup$ This is trivially true. The machine $H_{M,I}$ doesn't even have to consider its input. $\endgroup$
    – Yuval Filmus
    Nov 4, 2020 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, 2020 at 8:44

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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, 2020 at 9:27
  • $\begingroup$ You have to halt to output something, aren't you ? $\endgroup$
    – C Marius
    Nov 4, 2020 at 9:28
  • $\begingroup$ Oops, fixed it. $\endgroup$
    – Andrej Bauer
    Nov 4, 2020 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, 2020 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, 2020 at 9:56

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.