Church-Kleene ordinal: Difference between revisions
Jump to navigation
Jump to search
Content added Content deleted
RhubarbJayde (talk | contribs) No edit summary |
(Correction) |
||
| Line 1: | Line 1: | ||
<nowiki>The Church-Kleene ordinal, commonly denoted \( \omega_1^{\mathrm{CK}} \) or \( \omega_1^{ck} \) is defined as the supremum of all "</nowiki>[[Recursive ordinal|recursive]]<nowiki> ordinals". A recursive ordinal is the order-type of a well-order on the natural numbers which can be computed by a Turing machine. Note that all countable ordinals are the order-type of a well-order on the natural numbers, but there are only countably many Turing machines, and uncountably many countable ordinals, meaning there must be some ordinals which are still countable but they aren't recursive - i.e: they're so large that all well-orders they code are so complex that they are uncomputable. The least such is the Church-Kleene ordinal. Note that there is still a well-order on the natural numbers with order type \( \omega_1^{\mathrm{CK}} \) that is computable with an </nowiki>[[Infinite time Turing machine|''infinite time'' Turing machine]], since they are able to |
<nowiki>The Church-Kleene ordinal, commonly denoted \( \omega_1^{\mathrm{CK}} \) or \( \omega_1^{ck} \) is defined as the supremum of all "</nowiki>[[Recursive ordinal|recursive]]<nowiki> ordinals". A recursive ordinal is the order-type of a well-order on the natural numbers which can be computed by a Turing machine. Note that all countable ordinals are the order-type of a well-order on the natural numbers, but there are only countably many Turing machines, and uncountably many countable ordinals, meaning there must be some ordinals which are still countable but they aren't recursive - i.e: they're so large that all well-orders they code are so complex that they are uncomputable. The least such is the Church-Kleene ordinal. Note that there is still a well-order on the natural numbers with order type \( \omega_1^{\mathrm{CK}} \) that is computable with an </nowiki>[[Infinite time Turing machine|''infinite time'' Turing machine]], since they are able to compute whether a given Turing machine computes a well-order or not,<ref>Hamkins Lewis 2000, theorems that mention "\(\mathrm{WO}\)"</ref>. |
||
Also, note that given computable well-orders on the natural numbers with order types \( \alpha \) and \( \beta \), it is possible to construct computable well-orders with order-types \( \alpha + \beta \), \( \alpha \cdot \beta \) and \( \alpha^{\beta} \) and much more, meaning that the Church-Kleene ordinal is not pathological and in fact a limit ordinal, [[Epsilon numbers|epsilon number]], [[Strongly critical ordinal|strongly critical]], and more. |
Also, note that given computable well-orders on the natural numbers with order types \( \alpha \) and \( \beta \), it is possible to construct computable well-orders with order-types \( \alpha + \beta \), \( \alpha \cdot \beta \) and \( \alpha^{\beta} \) and much more, meaning that the Church-Kleene ordinal is not pathological and in fact a limit ordinal, [[Epsilon numbers|epsilon number]], [[Strongly critical ordinal|strongly critical]], and more. |
||