Church-Kleene ordinal: Difference between revisions

<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 solve the halting problem for ordinary Turing machines and thus diagonalize over the recursive ordinals.