0
$\begingroup$

Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs?

By a Halt1 oracle I mean that we have the ability to decide if Turing Machines with a Halting oracle halts or not.

$\endgroup$

1 Answer 1

1
$\begingroup$

I think that I have an answer to this, putting together my question helped me clarify things enough to come up with this idea

def X(T : TM0):
   for n = 0 and up:
      if !Halt0('T(n)')
        return

Now if we ask Halt1('X(T)') we should get an answer

  • yes => T diverges on some input
  • no => T halts on all inputs

Does this all make sense logically?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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