B-combinatory algebras. (English) Zbl 0654.03034

This work introduces a class of algebras generalizing both the applicative systems of the author’s earlier paper [C. R. Acad. Bulg. Sci. 37, 561-564 (1984; Zbl 0544.03020)] and the operative spaces studied in the reviewer’s book [Algebraic recursion theory (1986; Zbl 0613.03018)]. Namely, a B-combinatory algebra is a poset \({\mathcal F}\) augmented with fixed elements: A, C, D, O, I, \(D\check{\;}\), J, E, \(E_ 0\), \(E_ 1\), T, F, and monotonic operations: multiplication \(\lambda\phi\psi\cdot \phi\psi\) and branching \(\lambda\) \(\phi\) \(\psi\) \(\cdot (\phi,\psi)\) such that the following axioms hold: \(((A\phi)\psi)\chi =\phi (\psi \chi)\), \((C\phi)((D\psi)\chi)=(\phi \psi)\chi\), \(0\leq \phi\), \(\phi 0=0\), \(I\phi =\phi\), \((C\phi)(D \check{\;}\psi)=\phi \psi\), \((C\chi)(J(\phi,\psi))=(\chi \phi,\chi \psi)\), \(((E_ 0\chi)\phi,(E_ 1\chi)\psi)E=\chi (\phi,\psi)\), \((\phi,\psi)T=\phi\) and \((\phi,\psi)F=\psi\). The central result is an abstract version of the First Recursion Theorem.
Reviewer: L.Ivanov


03D75 Abstract and axiomatic computability and recursion theory