m (Undo revision 275256 by Triakula (talk) It is wrong. An oracle Turing machine actually can compute f_i(n) for all n. The point is not the computability for all n, but is more complicated.)
(One intermediate revision by one user not shown)
Line 33: Line 33:
== See also ==
== See also ==
*Wikipedia articles on {{w|Kleene's O}} and {{w|Church-Kleene ordinal}}.
{{Transfinite ordinals}}
{{Transfinite ordinals}}

Revision as of 07:56, January 16, 2020

Baptist Church

This church is not to be confused with logician Alonzo Church. It is probably very clean.

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\).

See also

Ordinals, ordinal analysis and set theory

Basics: cardinal numbers · normal function · ordinal notation · ordinal numbers · fundamental sequence · ordinal collapsing function
Theories: Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\Gamma_0\) · \(\vartheta(\Omega^3)\) · \(\vartheta(\Omega^\omega)\) · \(\vartheta(\Omega^\Omega)\) · \(\vartheta(\varepsilon_{\Omega + 1}) = \psi(\Omega_2)\) · \(\psi(\Omega_\omega)\) · \(\psi(\varepsilon_{\Omega_\omega + 1})\) · \(\psi(\psi_I(0))\)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^\text{CK}\) · \(\omega_\alpha^\text{CK}\) · \(\lambda,\zeta,\Sigma,\gamma\) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal · more...


Community content is available under CC-BY-SA unless otherwise noted.