Church-Kleene ordinal

An ordinal is considered recursive if it is the order type of a computable of a subset of the natural numbers. The Church-Kleene ordinal \(\omega_1^\text{CK}\), then, is the first ordinal that is not recursive.
An ordinal is recursive if and only if it is less than another recursive ordinal, so the Church-Kleene ordinal is also the supremum of all recursive ordinals, and the order type of the set of all recursive ordinals. It is a limit ordinal, since the successor of a recursive ordinal is also recursive. Since every computable well-ordering can be identified by a distinct , of which there are countably many, \(\omega_1^\text{CK}\) is also countable.
== Ordinal notation ==
A system called Kleene's \(\mathcal{O}\) gives us a non-recursive notation system over all recursive ordinals. Since an ordinal notation is required to be recursive, it is not an ordinal notation. Before constructing Kleene's \(\mathcal{O}\), first we need an enumeration \(f_0, f_1, f_2, \ldots\) of all the partial recursive functions. One way to do this is to order all the Turing machines lexicographically. Another way is to use Church numerals and order all closed lambda terms lexicographically by their Binary Lambda Calculus encoding.
Let \(K\) be the set of all notations, let \(<_\mathcal{O}\) be an operator indicating a well-founded strict partial ordering of \(K\), and let \(\mathcal{O}\) be a function mapping notations to ordinals. These three are defined inductively as follows:
* \(0 \in K\) and \(\mathcal{O}(0) = 0\).
* If \(n \in K\) and \(\mathcal{O}(n) = \alpha\), then \(2^n \in K\), \(\mathcal{O}(2^n) = \alpha + 1\), and \(n <_\mathcal{O} 2^n\).
* If for all natural numbers \(n\), we have \(f_i(n) \in K\) and \(f_i(n) <_\mathcal{O} f_i(n + 1)\), then \(3 \cdot 5^i \in K\), \(\mathcal{O}(3 \cdot 5^i) = \sup_{k \in \omega} \mathcal{O}(f_i(k))\), and for all \(k\) \(f_i(k) <_\mathcal{O} 3 \cdot 5^i\).
* \(a <_\mathcal{O} b\) and \(b <_\mathcal{O} c\) implies \(a <_\mathcal{O} c\).
=== Examples ===
From definition it follows that:
\(\matrix{\mathcal{O}(2^0) = 1 \\
\mathcal{O}(2^{2^0}) = 2 \\
\mathcal{O}(2^{2^{2^0}}) = 3 \\
\mathcal{O}(2^{2^{2^{2^0}}}) = 4 \\
\mathcal{O}(3 \cdot 5^i) = \omega}\)
Here \(i\) is an index of Turing machine that computes \(f_i(n) = 2 \uparrow\uparrow n\). Continuing,
\(\matrix{\mathcal{O}(2^{3 \cdot 5^i}) = \omega+1 \\
\mathcal{O}(2^{2^{3 \cdot 5^i}}) = \omega+2 \\
\mathcal{O}(2^{2^{2^{3 \cdot 5^i}}}) = \omega+3 \\
\mathcal{O}(2^{2^{2^{2^{3 \cdot 5^i}}}}) = \omega+4 \\
\mathcal{O}(3 \cdot 5^j) = \omega\cdot 2}\)
Here \(j\) is an index of Turing machine that computes \(f_j(n) = (2 \uparrow)^n (3 \cdot 5^i)\).
Continuing in this manner, it is possible to notate all recursive ordinals. The only issue is that indices of Turing machines are uncomputable; that is, we can't run over TM's via algorithm to verify that it actually computes needed function.
== Fundamental sequences ==
For each \(\alpha < \omega_1^\text{CK}\), if \(\alpha\) is a limit ordinal, then \(\alpha[n]\) is defined as \(\mathcal{O}(f_{i_{\alpha}}(n))\), where \(i_{\alpha}\) denotes the minimum of the non-empty set \(\{i \in K \mid \mathcal{O}(3 \cdot 5^i) = \alpha\}\).
Define \(g(0) = 0\) and \(g(n+1)\) as the smallest \(m \in K\) such that \(\mathcal{O}(g(n)) < \mathcal{O}(m)\). The fundamental sequence for \(\omega_1^\text{CK}\), then, is defined as \(\omega_1^\text{CK}[n] = \mathcal{O}(g(n))\).
=== Examples ===
Let's check how we define \(\omega[n] = \mathcal{O}(f_{i_{\omega}}(n))\).
Say that there is an ordering of Turing machines so that \(i_{\omega} = 1000\) and Turing machine with index \(1000\) computes \(2 \uparrow\uparrow n\). Then \(\omega[n] = \mathcal{O}(f_{1000}(n)) = \mathcal{O}(2 \uparrow\uparrow n) = 1+n\).
Say that there is another ordering of Turing machines so that \(i_{\omega} = 969\) and Turing machine with index \(969\) computes \(2 \uparrow\uparrow (n-1)\). Then \(\omega[n] = \mathcal{O}(f_{969}(n)) = \mathcal{O}(2 \uparrow\uparrow (n-1)) = n\).
Thus, fundamental sequences are dependent on ordering of Turing machines.
=== First few terms of fundamental sequence of Church-Kleene ordinal ===
By the definition, \(\omega_1^\text{CK}[0] = 0\). It turns out that \(\omega_1^\text{CK}[1] = 1\) and \(\omega_1^\text{CK}[2] = 2\) under any enumeration of Turing machines since 1 and 2 cannot be expressed in the form \(3 \cdot 5^n\). However, \(\omega_1^\text{CK}[3]\) depends on enumeration of Turing machines because \(3 = 3 \cdot 5^0\). If we fix, for example, \(f_0(n) = 2 \uparrow\uparrow n\), then \(\omega_1^\text{CK}[3] = \omega\).
== Fast-growing hierarchy ==
There is much wrong information on the fast-growing hierarchy \(f_{\omega_1^\text{CK}}\) with respect to the system of fundamental sequence above.
# The statement "\(f_{\omega_1^\text{CK}}\) is computable because every function in the fast growing hierarchy is computable" is wrong. A function in the fast-growing hierarchy is not necessarily computable even if it is associated to a recursive ordinal, and moreover \(\omega_1^\text{CK}\) is not recursive.
# The statement "\(f_{\omega_1^\text{CK}}\) is approximated to the busy beaver function because both of them are uncomputable functions diagonalising computable functions" is wrong. The system of fundamental sequences above heavily depends on the choice of the enumeration of Turing machines, and so does the growth rate of \(f_{\omega_1^\text{CK}}\). For example, it is known that it can be bounded by \(f_{\omega+3}\) in Wainer hierarchy if one chooses a specific enumeration of Turing machines.T. Kihara, omega-1-ck.pdf. At least, there is no known enumeration of Turing machines for which \(f_{\omega_1^\text{CK}}\) is approximated to the busy beaver function.
# The statement "\(f_{\omega_1^\text{CK}}\) grows faster than any computable function because it diagonalises all computable functions in the fast-growing hierachy" is wrong. As we explained above, it can be bounded by \(f_{\omega+3}\) in Wainer hierarchy. The diagonalisation sometimes causes the decreasing of growth rates.
# The statement "\(f_{\omega_1^\text{CK}}\) is bounded by the second order busy beaver function because it can be computable by an oracle Turing machine" is wrong. Such a comparison has never been verified for a specific non-pathologic enumeration of Turing machines. We do not even know whether \(f_{\omega_1^\text{CK}}\) is bounded by the \(\alpha\)-th order busy beaver function for some ordinal \(\alpha\) below \(\omega_1^\text{CK}\) or not with respect to a non-pathologic enumeration of Turing machines, because no notation up to \(\omega_1^\text{CK}\) is computable by a higher order oracle Turing machine whose order is smaller than \(\omega_1^\text{CK}\).
Namely, the growth rate of \(f_{\omega_1^\text{CK}}\) with respect to a non-pathologic enumeration of Turing machines is unknown in the sense that the least ordinal \(\alpha\) such that \(f_{\omega_1^\text{CK}}\) is bounded by the \(\alpha\)-th order busy beaver function is unknown. At least, if a given function \(f\) irrelevant to \(f_{\omega_1^\text{CK}}\) is verified to grows faster than \(f_{\omega_1^\text{CK}}\), then it usually grows significantly faster than the busy beaver function because we usually need a stronger tool than higher order oracle Turing machines in order to study such an \(f\).
However, \(f_{\omega_1^\text{CK}}\) (with respect to any system of fundamental sequences) necessarily grows at least as fast as \(f_\omega\) in Wainer hierarchy because the fundamental sequence of \(\omega_1^\text{CK}\) is monotonically increasing.
== References ==
== External links ==
*Wikipedia articles on and 
*Church-Kleene ordinal defined in Binary Lambda Calculus
ja:チャーチ・クリーネ順序数
Category:Transfinite ordinals