Basic recursion theory in partially ordered models of some fragments of the combinatory logic. (English) Zbl 0544.03020

This paper is a brief abstract of a part of the author’s dissertation aimed to establish some basic results of Recursion Theory in the case of combinatory incomplete partially ordered applicative systems. The main difference of these algebraic systems from the related ones studied by D. Skordev [Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 24, 23-31 (1976; Zbl 0328.02026)] and the reviewer [C. R. Acad. Bulg. Sci. 33, 735-738 (1980; Zbl 0449.03042)] is the lack of associativity. Considered are preassociative systems - partially ordered sets \({\mathcal F}\) with a monotonous operation multiplication, a least element 0 and combinators A (associator), C, D, s.t. \(((A\phi)\psi)\chi =\phi(\psi \chi)\) and \((C\phi)((D\psi)\chi)=(\phi \psi)\chi\) for all \(\phi,\psi,\chi \in {\mathcal F}\). (The case of systems in which \((C\phi)\psi =\psi \phi\) holds is treated separately.) The so called natural preassociative systems have in addition elements Z, S, Z’, S’, C’ satisfying certain axioms. An extension \({\mathcal F}_ 1\) of \({\mathcal F}\) is iterative iff for all \(\phi,\psi,\chi \in {\mathcal F}\) the systems \(\phi \leq \vartheta\), \(\psi \leq \vartheta\) and \(\phi \leq \vartheta\), \((\psi \vartheta)\chi \leq \vartheta\) have solutions \(\phi \vee \psi\), \(I_ 3(\phi,\psi,\chi)\) in \({\mathcal F}\) minimal in \({\mathcal F}_ 1\). Proposition 2 (First Recursion Theorem). Let \({\mathcal F}\) be a natural preassociative system with a right zero 0, \({\mathcal E}\subseteq {\mathcal F}\) and \({\mathcal F}_ 1\) be an iterative extension of \({\mathcal F}\) which has an associator in \({\mathcal F}\). Let \(\max \{\vartheta /\alpha \vartheta \leq \phi \}\) and \(\inf_{n}\phi_ n\) exist in \({\mathcal F}_ 1\) and whenever 0\(\alpha \leq \phi\), then \(\max \{\vartheta /\vartheta \alpha \leq \phi \}\) exist in \({\mathcal F}_ 1\) for all \(\alpha \in {\mathcal F}\), \(\phi,\phi_ 0,...,\in {\mathcal F}_ 1\). Then each system of the form \(\Gamma_ i(\vartheta_ 1,...,\vartheta_ n)\leq \vartheta_{k_ i}\), \(1\leq k_ i\leq n\), \(1\leq i\leq m\), where \(\Gamma_ i(\vartheta_ 1,...,\vartheta_ n)\) are constructed from \(\vartheta_ 1,...,\vartheta_ n\) and members of \({\mathcal E}\) by multiplication, has a solution \(\phi_ 1,...,\phi_ n\) in \({\mathcal F}\) minimal in \({\mathcal F}_ 1\) and s.t. \(\phi_ 1,...,\phi_ n\) are obtained from A, C, D, Z, S, Z’, S’, C’ and members of \({\mathcal E}\) by multiplication, V and \(I_ 3\). Proposition 3 is an Enumeration and Second Recursion Theorem. (The set \({\mathcal E}\) in its formulation should be assumed finite.) Proposition 4 establishes the representability of all partial recursive functions. Several examples of applicative systems meeting the above assumptions are adduced.
Reviewer: L.Ivanov


03D75 Abstract and axiomatic computability and recursion theory