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!


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.