Consider such an oracle:

Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.

  1. How strong is a TM with the oracle?
  2. Can the oracle exist(or does the question always have an answer) if change [1] into a TM with the oracle?

Some results I get:

  1. It's as strong as a TM with oracle that compare running time of two programs, or arbitary returned value if both don't halt.
  2. If the oracle returns integer the TM returns(may need to define a way it outputs integer), or arbitary integer if it doesn't halt, we can solve the halting problem by getting the runtime and check. However, currently I can't output from the oracle a string of any finite length if the length can be arbitary long, promising it's finite.

(Moved from here)

  • $\begingroup$ Try asking it in the computer science branch of stack-exchange $\endgroup$ Aug 8 '19 at 15:37
  • $\begingroup$ @BadAtGeometry Moved. $\endgroup$
    – l4m2
    Aug 8 '19 at 15:40
  • $\begingroup$ @NoahSchweber It's currently in both SE, not sure what'd happen $\endgroup$
    – l4m2
    Aug 8 '19 at 16:10
  • $\begingroup$ I don't understand the non-yellow part. If you mean an oracle returning the number of steps before the program halts (if it does) and if it doesn't halt return anything (but always return something) then your oracle is the oracle for the halting problem. Then you can construct recursively a new oracle for those programs using the oracle during their execution. $\endgroup$
    – reuns
    Aug 8 '19 at 23:14

This same question appears on cs.stackexchange; see my answer to it there for details. Since we can't close as a duplicate of a question on another site, I've made this answer community wiki to avoid double-dipping reputation.

These are exactly the PA degrees - the Turing degrees which compute some complete consistent extension of (first-order) Peano arithmetic. The class of PA degrees is incredibly important in computability theory and has a number of equivalent characterizations, with possibly the most useful being:

$X$ has PA degree iff for every computable infinite binary tree $T$, there is an infinite path through $T$ computable relative to $X$.

Although always non-computable (this is Rosser's improvement of Godel's incompleteness theorem), PA degrees can be very weak - in particular, they can be low. There are also PA degrees which are Turing incomparable with the halting problem.


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.