This book presents a detailed exposition of the author’s elegant index- free axiomatical approach to Recursion Theory announced earlier [Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 24, 23-31 (1976; Zbl 0328.02026)].
The introductory Chapter I describes uniformly the notions of partial recursiveness, recursive enumerability and prime and search computability of Moschovakis, thus paving the way for an abstract concept of effective computability.
Chapter II. The algebraic system of combinatory space (CS) is introduced and studied. This is a quasi-ordered semigroup \({\mathcal F}\) with a unit I, a right sufficient subset \({\mathcal C}\) of \({\mathcal F}\) (whenever \(\phi\) \(X\leq \psi X\) for all \(X\in {\mathcal C}\), then \(\phi\leq \psi)\), two additional operations \(\Pi\), \(\Sigma\) over \({\mathcal F}\) and fixed elements L,\(R\in {\mathcal F}\) and T,\(F\in {\mathcal C}\) satisfying several axioms. A remarkable feature of this system is its abundance in interesting models. Among the considered examples are CS consisting of multiple-valued functions, probabilistic functions, fuzzy binary relations as well as spaces connected with complexity measuring of data processing, \(\forall\)- definiteness and reliable estimation of functions. A ’standard’ example: given a set M, injective \(J:M^ 2\to M\) with reversies L, R and \(a\neq b\in M\), take \({\mathcal F}=\{\phi /\phi:M\to M\}, \phi\leq \psi\) iff \(\psi\) is an extension of \(\phi\), \(\phi \psi =\lambda s.\phi(\psi(s)), I=\lambda s.s, {\mathcal C}=\{\lambda s.\cdot t/t\in M\}, \Pi(\phi,\psi)=\lambda s.J(\phi(s),\psi(s)), \Sigma(\chi,\phi,\psi)(s)=t\) iff \(\chi(s)=a \& \phi(s)=t \vee \chi(s)=b \& \psi(s)=t, T=\lambda s.a\) and \(F=\lambda s.b.\)
Chapter III. From the Recursion Theory viewpoint those CS are important in which certain monotonous mappings over \({\mathcal F}\) have least fixed points (lfp). Existence of lfp is provided by well known theorems due to Tarski and Kleene (the continuous version). What is however stressed by the author is accessibility of lfp which allows to prove properties by \(\mu\)-induction. On these lines the basic notion of iterative CS (ICS) is introduced by an additional second order axiom: a CS is iterative iff for all \(\phi\),\(\chi\) the lfp [\(\phi\),\(\chi]\) (iteration of \(\phi\) controlled by \(\chi)\) of the mapping \(\lambda \theta.\Sigma(\chi,I,\theta \phi)\) exists and is accessible. Basic properties of iteration are established to be used in the sequel. CS from Chapter II are shown to be iterative, and iteration in particular examples is explicitly characterized. In the example outlined above \([\phi,\chi](s)=\phi^ n(s),\) provided \(\forall i<n (\chi \phi^ i(s)=b)\) and \(\chi \phi^ n(s)=a.\)
Chapter IV. Relative recursiveness is introduced and studied as a principal abstract concept of effective computability, where an element \(\phi\) is recursive in a subset \({\mathcal B}\) of \({\mathcal F}\) iff it can be obtained from L, R, T, F and members of \({\mathcal B}\) by making use of the operations \({\mathbb{O}}\), \(\Pi\), \(\Sigma\), []. The notion of a mapping over \({\mathcal F}\) recursive in \({\mathcal B}\) is introduced via parametrization. Normal Form Theorems proved in this chapter ensure that, roughly speaking, it suffices to apply iteration just once. The relative recursiveness in specific ICS is characterized to give that classical concepts of effective computability (such as relative \(\mu\)- recursiveness, enumeration reducibility, prime and search computability) are particular instances.
In Chapter V the author develops an intrinsic recursion theory on ICS the central result of which is a First Recursion Theorem asserting that all unary mappings when recursive in \({\mathcal B}\) have lfp recursive in \({\mathcal B}\). A Second Recursion Theorem and an Enumeration Theorem are given, too. Representability of all partial recursive functions is established, bringing the consequences of undecidability and lack of recursive axiomatizability. Finally, the notion of search computability is generalized by considering ICS in which \({\mathcal C}\) has a union.
The book will be of interest for recursion theorists as a step toward adequate independent foundations of Recursion Theory. Computer scientists may also benefit, particularly from the paragraphs on McCarthy’s equivalences and the so called Böhm-Jacopini spaces. (It should be added that Backus’s systems for functional programming are studied by making use of the ’standard’ ICS in a paper of D. Skordev in: Mathematical theory and practice of software systems, ed. A. P. Ershov, Novosibirsk (1982).) A refined version of ICS proposed by the author [C. R. Acad. Bulg. Sci. 33, 739-742 (1980; Zbl 0452.03037)] accounts, as shown by the reviewer, for the Kleene-recursiveness in higher types. Besides that, Skordev’s approach has recently inspired the rise of related ones due to the reviewer [ibid. 33, 735-738 (1980; Zbl 0449.03042)] and Y. Zashev [ibid. 37, 561-564 (1984)].