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.

  • 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$ Jun 3 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
    Jun 3 at 12:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.