## FANDOM

10,673 Pages

An ordinal is considered recursive if it is the order type of a computable well-ordering 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 always recursive if it is less than another recursive ordinal, so the Church-Kleene ordinal is also the supremum 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 Turing machine, 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.

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$$.

## 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}(i) = \alpha\}$$.

Define $$g(0) = 0$$ and $$g(n+1)$$ as the notation with smallest $$m \in \mathbb{N}$$ such that $$m \in K$$ and $$\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))$$.

## Fast-Growing Hierarchy

There are many wrong informations on the fast-growing hierarchy $$f_{\omega_1^\text{CK}}$$ with respect to the system of fundamental sequence above.

1. 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.
2. 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.[1] At least, there is no known enumeration of Turing machines for which $$f_{\omega_1^\text{CK}}$$ is approximated to the busy beaver function.
3. 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.
4. 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$$.