<p>There is a talk given by Stephen Simpson, located here <a href="http://www.personal.psu.edu/t20/talks/pisa0104/talk.pdf" rel="nofollow">http://www.personal.psu.edu/t20/talks/pisa0104/talk.pdf</a>, where he discusses the relative consistency strengths of various subsystems of second-order arithmetic $Z_2$. In particular, the theory $\Pi^1_1-CA_0$ denotes a subsystem of $Z_2$ whose set of true $\Pi^1_0$-consequences is of Turing degree $\emptyset^{(\omega^{CK}_{1})}$, which is the Turing degree corresponding to Kleene's $\mathcal O$. However, no proof is given, but I'm sure that one can be found in his bibliography for the talk (or perhaps even in his text on reverse mathematics <a href="http://www.personal.psu.edu/t20/sosoa/" rel="nofollow">http://www.personal.psu.edu/t20/sosoa/</a>). </p>

<p>The relevant information in the PDF is on page 29.</p>

CC BY-SA 3.0
2016-08-19T15:54:50.037Z
2016-08-19T15:54:50.037Z
cmn1
<p>It's not computable whether a number is a member of Kleene's ${\mathcal {O}}$. What is that set's Turing degree? I can almost see an argument that ${\mathcal {O}} \leq_T \emptyset^{(2)}$ but I can't see how to be sure that the set I'm thinking of is the smallest that meets the criteria. It also seems plausible that ${\mathcal {O}} =_T \emptyset^{(\omega_{CK})}$. Is this known?</p>

CC BY-SA 3.0
2016-08-09T02:18:14.880Z
https://en.wikipedia.org/wiki/Kleene%27s_O
Kaveh
CC BY-SA 3.0
2016-08-09T02:25:48.140Z
$\mathcal{O}$ is $\Pi^1_1$-complete. Not sure what you mean by $\emptyset^{\omega_{CK}}$. To define jumps at limit ordinals you need fundamental sequences, you cannot just plug in an arbitrary ordinal there. See ch. 1 of vol. 2 of Classical Recursion Theory.
Kaveh
<hypercomputation>
What is the Turing degree of Kleene's O?
Paul Crowley
# What is the Turing degree of Kleene's O?

(Asked by: username_0 on 2016-08-09)

It's not computable whether a number is a member of Kleene's ${\mathcal {O}}$. What is that set's Turing degree? I can almost see an argument that ${\mathcal {O}} \leq\_T \emptyset^{(2)}$ but I can't see how to be sure that the set I'm thinking of is the smallest that meets the criteria. It also seems plausible that ${\mathcal {O}} =\_T \emptyset^{(\omega\_{CK})}$. Is this known?

**Tags:** hypercomputation
> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Kleene%27s_O  
> **username_1**: $\mathcal{O}$ is $\Pi^1_1$-complete. Not sure what you mean by $\emptyset^{\omega_{CK}}$. To define jumps at limit ordinals you need fundamental sequences, you cannot just plug in an arbitrary ordinal there. See ch. 1 of vol. 2 of Classical Recursion Theory.  

---

## 1 answers

### Answer by username_2 on 2016-08-19. Score: 4

There is a talk given by Stephen Simpson, located here <http://www.personal.psu.edu/t20/talks/pisa0104/talk.pdf>, where he discusses the relative consistency strengths of various subsystems of second-order arithmetic $Z\_2$. In particular, the theory $\Pi^1\_1-CA\_0$ denotes a subsystem of $Z\_2$ whose set of true $\Pi^1\_0$-consequences is of Turing degree $\emptyset^{(\omega^{CK}\_{1})}$, which is the Turing degree corresponding to Kleene's $\mathcal O$. However, no proof is given, but I'm sure that one can be found in his bibliography for the talk (or perhaps even in his text on reverse mathematics <http://www.personal.psu.edu/t20/sosoa/>).

The relevant information in the PDF is on page 29.


---

