2
$\begingroup$

Certain real numbers can be approximated arbitrarily well by computable functions. If we introduce halting oracles, then more real numbers can be "computed", like Chaitin's constant or the limit of the Speckner sequence.

Using Turing machines for simplicity, we can define an order-$\alpha$ oracle Turing machine for a countable ordinal $\alpha$ to be a Turing machine that can access an oracle to solve the halting problem for any order-$\beta$ oracle Turing machine where $\beta<\alpha$. (This can be done by, say, taking a bijection between the integers and the ordinals less than $\alpha$ and using consecutive symbols on the tape to encode ordinals.)

Let's define the computability ordinal of a real number to be the smallest $\alpha$ such that there exists an order-$\alpha$ oracle Turing machine that approximates it infinitely well. Does there exist a (countable) computability ordinal for every real number?

This follows from the Axiom of Constructibility (related question V=L and a Well-Ordering of the Reals). I think it looks likely equivalent to AoCon, as if every real has a computability ordinal then we can use that and a numbering of the Turing machines to well-order the reals, but I don't know how to prove it.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The question of which reals have which order depends a lot on how the ordinals are coded by natural numbers. You haven't specified the hierarchy sufficiently to determine a precise hierarchy. For example, any given real can be made to have order $\omega+1$ or whatever, if you use a coding of this ordinal that enables this. We don't in general have canonical choices of coding of countable ordinals by natural numbers, and this will strongly affect the hierarchy. $\endgroup$
    – Joel David Hamkins
    Commented Jun 3, 2023 at 11:42
  • 2
    $\begingroup$ The paper “Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees” by Harold Hodes (J. Symbolic Logic 45 (1980) 204–220) properly defines the $\alpha$-th iteration of the Turing jump for all $\alpha<\omega_1^L$, and should at least partially answer your question, but as Joel David Hamkins points out, there are subtleties in how things are coded, you can't blindly assume a phrase such as “the halting problem for any order-$β$ oracle Turing machine” to be meaningful $\endgroup$
    – Gro-Tsen
    Commented Jun 3, 2023 at 12:39

0

Reset to default

You must log in to answer this question.