4
$\begingroup$

For the sake of clarity, I am regarding a computable relation on $\mathbb{N}$ as a $2$-symbol ($0$ and $1$) Turing machine $T$ which halts on any initial binary string (which are interpreted as some fixed binary enumeration of $\mathbb{N} \times \mathbb{N}$ such as Cantor's zigzag). The final symbol written down before the machine halts is regarded as its "output".

So this Turing machine can be regarded as a function $T : \mathbb{N} \times \mathbb{N} \rightarrow \{0,1\}$, and therefore a relation on $\mathbb{N}$ where $n \sim_T m \iff T(n,m) = 1$.

My question starts with the following thought:

Can I construct a Turing machine $W$ where:

Given an arbitrary Turing machine $T$ as input, $W$ outputs $1$ if $T$ determines a well-ordered relation on $\mathbb{N}$ and outputs $0$ otherwise.

Now the answer to this question is no if $W$ is required to be a regular Turing machine, as $W$ has to determine whether $T$ always halts amongst other criteria. But what if we allow a potential construction of $W$ to include a certain level of halting oracle?

When I say a certain level, I'm follow the same line of reasoning as Scott Aaronson when he defines super oracles and super busy beaver functions $BB_1(n),BB_2(n),\dots$.

Essentially $BB_0(n)$ is the standard busy beaver function and then we inductively define:

  1. $\mathcal{O}_k$ as an oracle which given $n$ as input, outputs $BB_k(n)$
  2. $BB_{k+1}(n)$ as the maximum number of steps a $2$-symbol $n$-state Turing machine can perform before halting when the Turing machine has access to $\mathcal{O}_k$

Now here is my actual question:

Does there exist $K \in \mathbb{N}$, such that I construct a $\mathcal{O}_K$-Turing machine $W$ where:

Given an arbitrary (ordinary, no oracle) Turing machine $T$ as input, $W$ outputs $1$ if $T$ determines a well-ordered relation on $\mathbb{N}$ and outputs $0$ otherwise.

Let's break this down as a checklist for what $W$ needs to consider:

  • Does $T$ halt on every initial string?
  • Is $\sim_T$ a reflexive relation?
  • Is $\sim_T$ a transitive relation?
  • Is $\sim_T$ a antisymmetric relation?
  • Is $\sim_T$ a total relation?
  • Does there exist an infinitely long strictly decreasing sequence for $\sim_T$?

The first bullet point can be realized by an $\mathcal{O}_2$-Turing machine, by first constructing a $\mathcal{O}_1$-Turing machine (denoted $H$) which checks if each initial string one halts one by one and $H$ halts if it finds an initial string which doesn't halt. Then construct a $\mathcal{O}_2$-Turing machine which checks if $H$ halts.

The second through to fifth bullet points can be realized by $\mathcal{O}_1$-Turing machines. For example checking transitivity can be done by first constructing a Turing machine which checks every triplet of inputs of the form $(a,b), (b,c), (a,c)$ and halts if $T(a,b)=1, T(b,c)=1, T(a,c)=0$.

But what about the final bullet point?

The final bullet point seems trickier, but the reason why it seems potentially feasible to me is because computable sequences have bounded growth rate (for example by the busy beaver function).

My thought process is if $T$ is a Turing machine satisfying the first five bullet points and $\sim_T$ has a strictly decreasing sequence, does there then necessarily exist a (possibly different) strictly decreasing sequence which is eventually dominated by $BB_0(n)$? If not, what about $BB_K(n)$ for some $K \in \mathbb{N}$?

If so, then it would indeed be possible to find an oracle Turing machine which addresses the final bullet point. To do this construct a sequence of oracle Turing machines $(Or_m)_{m=0}^\infty$ such that if $Or_m$ is given an input $n$, then $Or_m$ finds the immediate $\sim_T$ predecessor from $\{ 1,...,m+BB_K(1) \}$, then the $\sim_T$ predecessor of that input from $\{ 1,...,m+BB_K(2) \}$, etc. By asking enough halting questions about this sequence of oracle Turing machines, we would have addressed the final bullet point.

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ The set of (indexes of) recursive ordinals, aka Kleene's $\mathcal{O}$, is $\Pi^1_1$-complete, so you would need an oracle for a $\Pi^1_1$-complete set. $\endgroup$
    – Benedict Eastaugh
    Commented Aug 30, 2023 at 13:17
  • $\begingroup$ @BenedictEastaugh Thank you. Then I guess my question is equivalent to asking if any of the oracles in my question $\mathcal{O}_0, \mathcal{O}_1, \dots$ are strong enough to encode a $\Pi_1^1$-complete set. Is that known? $\endgroup$
    – Sam Forster
    Commented Aug 30, 2023 at 13:20
  • 7
    $\begingroup$ @SamForster What you denote $\mathcal{O}_k$ represents the Turing degree $\mathbf{0}^{(k)}$, i.e., the $k$-th Turing jump of $\mathbf{0}$. These are all far below Kleene's $\mathscr{O}$, whose degree is $> \mathbf{0}^{(\gamma)}$ for every $\gamma < \omega_1^{CK}$ (the Church-Kleene ordinal). To learn more about all this, I recommend Hinman's book Recursion-Theoretic Hierarchies (1978). $\endgroup$
    – Gro-Tsen
    Commented Aug 30, 2023 at 13:28
  • $\begingroup$ @Gro-Tsen Thank you, I'll check it out. $\endgroup$
    – Sam Forster
    Commented Aug 30, 2023 at 13:42
  • 5
    $\begingroup$ The first chapter of Sacks' book Higher recursion theory is also a great source on this; both books, incidentally, are freely-and-legally available from projecteuclid. $\endgroup$
    – Noah Schweber
    Commented Aug 30, 2023 at 14:10

1 Answer 1

Reset to default
6
$\begingroup$

To move this one off the unanswered queue:

No, the halting problem is much too weak to do this. Determining whether a computable linear order is a well-order is $\Pi^1_1$-complete, and in particular strictly more difficult than any computable iterate of the Turing jump (see "hyperarithmetic hierarchy").

Both Hinman's Recursion-theoretic hierarchies and Sacks' Higher recursion theory are good resources on this topic, and are freely-and-legally available

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .