2
$\begingroup$

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 to here)

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ See this and this. $\endgroup$ – dkaeae Aug 8 '19 at 15:47
  • $\begingroup$ @dkaeae How does that help? $\endgroup$ – l4m2 Aug 8 '19 at 15:52
  • $\begingroup$ Your oracle is not computable. I would guess that it is strictly weaker than a halting oracle, that is, you cannot solve the halting problem with an oracle to your problem. $\endgroup$ – Yuval Filmus Aug 8 '19 at 23:50
2
$\begingroup$

EDIT: I made a deeply silly mistake in my previous answer. Below what I've done is answered the question, then explained how two variations of the question - which I originally conflated with the actual question - yield a very different answer.

An oracle of the type you describe computes the halting problem (and conversely every oracle computing the halting problem computes an oracle of your type).

  • Suppose $x$ computes the halting problem. Without loss of generality, we may take $x$ to literally be the halting problem. Then we can compute an $f$ as desired by simply taking an input $e$, asking $x$ whether $T_e(e)$ halts, and (i) if the answer is no, halt and output $0$ and (ii) if the answer is yes, run $T_e$ until it halts and output the result.

  • Conversely, suppose $f$ has the desired property. There is a total computable function $h$ such that for all $e$ if $T_e(e)$ halts, then $T_{h(e)}(h(e))$ halts and gives the runtime of $T_e(e)$. Now to tell whether $T_e(e)$ halts we simply run $T_e(e)$ for $f(h(e))$-many steps.

Now there are a couple natural variations to the above notion:

  • What if we demand inequality instead of equality?

  • What if we restrict attention to machines with binary output?

Both of these variations prevent the argument above from working, the former by preventing us from representing runtimes as outputs and the latter by preventing us from coding literally anything into the output.

It turns out that these notions yield a much weaker complexity class: namely the PA degrees. The original definition was that something is of PA degree if it computes a complete consistent extension of Peano arithmetic (which by Godel must be non-computable), but there are many equivalent definitions. Generally the simplest to work with is:

A degree ${\bf a}$ is PA iff whenever $X$ is an infinite computable binary tree, ${\bf a}$ computes an infinite path through $X$.

PA degrees can be quite weak, computability-theoretically. While no PA degree is computable, they don't have to compute the halting problem: there are PA degrees incomparable with the halting problem, and there are PA degrees strictly weaker than the halting problem (where strength here is measured by Turing reducibility).

Re: relativization, the answer is no: the proof of the incomputability of all PA degrees relativizes, so no oracle is PA over itself.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ keep in mind that Te's output on input e might be unrelated to the runtime of Te(e). Yet the output can be the runtime, so I don't quie understand the part $\endgroup$ – l4m2 Sep 7 '19 at 17:05
  • $\begingroup$ We can write function $g$ that output how many steps to run $f$ $\endgroup$ – l4m2 Sep 8 '19 at 11:45
  • $\begingroup$ @l4m2 Ouch! That's embarrassing. When I get a moment I'll repair this answer, but very briefly: if we look instead at functions which avoid the value, or restrict attention to $\{0,1\}$-valued Turing machines, then the statements above are correct. I was writing without thinking and failed to realize that I was mixing up circumstances. $\endgroup$ – Noah Schweber Sep 8 '19 at 17:00
  • 1
    $\begingroup$ @YuvalFilmus Consider the tree $D$ of finite binary sequences where a binary sequence $\sigma$ of length $n$ is on $T$ iff for each $k<n$, it is not the case that running $T_k(k)$ for $n$ steps halts and yields $\sigma(k)$. Infinite paths through $D$ are exactly the $\{0,1\}$-valued functions which avoid every recursive function in the desired way ("diagonally nonrecursive on $\{0,1\}$," or "DNR$_2$"). Now apply the low basis theorem. $\endgroup$ – Noah Schweber Sep 8 '19 at 17:54
  • 1
    $\begingroup$ That does the former case, where we want to avoid the functions' outputs. But by staying in $\{0,1\}$ we've also shown how to do the latter: look at the "dual" tree where we replace $\sigma(k)$ by $1-\sigma(k)$. $\endgroup$ – Noah Schweber Sep 8 '19 at 17:55

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.