# How strong is an oracle that avoid don't-halt

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.
• Try asking it in the computer science branch of stack-exchange Aug 8 '19 at 15:37
– l4m2
Aug 8 '19 at 15:40
• @NoahSchweber It's currently in both SE, not sure what'd happen
– l4m2
Aug 8 '19 at 16:10
• 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. Aug 8 '19 at 23:14

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