A problem I may need to rectract the results of the previous blog post because the transfinitary combinator calculus is way too strong. Let’s take a certain combinator. This maps an ordered pair \((a,b)\) where \(b\) is a representation of true or false and \(a\) is a representation of a Turing machine state. The combinator […]
Revisiting the transfinite combinator calculus Read More »
I’m back with another topic concerning ordinals! The transfinite combinator calculus The transfinite combinator calculus is an extension of normal combinator calculus. We define several related concepts as follows: If an expression \(x\) is beta-reducible, then \(\operatorname{cof}(x)=\operatorname{cof}(\operatorname{reduce}(x))\) and \(x[\alpha]=\operatorname{reduce}(x)[\alpha]\). If \(y\) is a limit, then \(\operatorname{cof}(xy)=\operatorname{cof}(y)\) and \((xy)[\alpha]=x(y[\alpha])\). If \(x\) is a limit, \(y\) is
Transfinite combinators and admissible ordinals Read More »
Hello, I’m back (who could have expected?) with my new OCF (Not an ordinal notation.). We follow several conventions from the world of OCFs. First, let $$\Omega_\nu=\begin{cases} 1 & \mbox{if }n=0 \\ \aleph_\nu & \mbox{otherwise}\end{cases}$$ And let \(\Omega=\Omega_1\). Then we define the function \(\psi_\nu(\alpha)\) as the least ordinal that cannot be constructed by: All ordinals