4
$\begingroup$

All ideas explained below are due to A.P.Goucher, and defined here.

First of all, $SKI\Omega$ calculus is an extension of standard SKI calculus, with additional type of combinator, called oracle combinator. It takes three arguments, and $\Omega xyz$ reduces to $y$ if tree $x$ eventually becomes a lone I combinator, and otherwise it reduces to $z$.

Because there are no restrictions on $x$, it might be possible (and indeed sometimes happens) that tree P at one point asks the oracle combinator about its own halting, which can lead to paradoxes. To avoid that, we define rank of $SKI\Omega$ tree by transfinite recursion as follows: if a tree never makes an oracle query, we define its rank to be 0. If a tree only ever queries the oracle combinator about trees of rank $<\alpha$, then it has rank $\alpha$. We can also define proper rank to be the minimal rank which a tree has, if it has any. Trees with ranks are well-founded. Such paradoxical trees as I explained above, have no rank at all. They are ill-founded.

In connection to some other problem, I've been wondering: what is the upper bound of a well-founded tree? To be more specific, what is the smallest ordinal which isn't a minimal rank of any tree? Or, equivalently, smallest ordinal $\alpha$ such that, if any $SKI\Omega$ tree has a rank, then it has rank $<\alpha$?

The only guess I have is that this $SKI\Omega$ calculus is $\Delta_1^1$, and thus the ordinal would be bounded by $\omega_1^{CK}$, but I have no idea how to show this. It might be also a larger admissible ordinal, or limit of such, but for that I have even less idea on dealing with this.

Thanks in advance for any help!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.