About thirty years ago, logicians and computer scientists, more or less independently, began to study systematically computability and computations on abstract algebraic structures. The papers Fraïssé [1961], Lacombe [1964, 1964 a], Kreisel [1965] are among the earliest in this direction, which are written by logicians, and the papers Ershov [1958] and Mc Carthy [1962, 1963] are among the first ones, which approached the same problems from the other side. A series of other essential contributions to the field have been produced, and a theory of computability arose, generalizing the ordinary recursive function theory (the monographs Fenstad [1980] and Fitting [1981] give a comprehensive account of certain directions of this general theory).
The present book is a monograph on a further generalization of a part of the general theory in question, namely of the theory of abstract first order computability from the paper Moschovakis [1969]. When reading that paper, the present author was, in particular, intrigued by the use made of multiple-valued functions. In 1974, he observed certain useful algebraic properties of the operations on such functions. This step enabled him to make a further one, namely to generalize certain notions and results of the theory of the abstract first order computability in such a way that also the role of functions can be played by objects of some more general nature. It has been proposed to use as such function-like objects the elements of appropriate partially ordered algebraic structures, called combinatory spaces. Among all possible combinatory spaces, the so-called iterative ones turned out to be suitable for the development a theory of computability. Various examples of such structures have been found, and the intuitive idea about most of these examples can be described as follows.
It is usual to study data processing devices (in particular, computational procedures) by means of some mathematical models which describe their behaviour. The most frequently used model is the input-output relation showing which are the possible output data corresponding to any concrete instance of the input data (in the case of a deterministic device, this relation is the graph of a partial function). One could supplement this model with information about those instances of the input data at which some unpleasant effects during the work of the device are possible, such as, for example, unproductive termination, the presence of a failure or entering into an infinite loop. A further model arises if, in conjunction with this, one neglects information about the possible output data corresponding to such unsafe instances of the input data and removes this information from the model. In the case of a probabilistic device, the appropriate mathematical model would be not a relation, but a real-valued function showing, for each concrete instance of the input data, which are the probabilities of the various possible output data. Many other kinds of mathematical models can turn out to be appropriate in different situations. An important point is that there are some widely used ways of combining data processing devices, and to this ways usually some operations on the mathematical models of the devices correspond. For example, one can usually define an associative operation of composition of the mathematical models, which corresponds to sequential composition (piping) of the devices. In most examples of combinatory spaces, the elements of the space can be regarded as possible mathematical models (of some fixed kind) corresponding to concrete data processing devices, and the algebraic operations on these elements will correspond to some ways of combining the devices.
The above intuitive idea gives an explanation of our choice of the term "combinatory space". The adjective "combinatory" is connected with combining the devices, and there is no close connection between our theory and Combinatory Logic (although similarities in certain respects can be observed). A combinatory space can be regarded as a system for functional programming, dealing with some kind of function- like objects, and the FP-systems from Backus [1978] are a particular case of this.
A mathematical theory of a general nature must be justified by the existence of sufficiently many examples. But this is not enough. The theory must also contain serious mathematical results. We hope that such is the case of the theory of combinatory spaces. At this moment we cannot enter into details, and we shall only mention that our generalization of the recursive function theory contains (among others) such results as the First Recursion Theorem, Normal Form Theorems, Theorem on Existence of Universal Computable Elements with Second Recursion Theorem. Moreover, the corresponding results from the ordinary recursive function theory and from Moschovakis' theory of the abstract first order computability can be obtained as particular instances. We note also that the notions of prime and search computability from the latter theory obtain characterizations, which are simpler and easier to use than the definitions in the paper Moschovakis [1969].
As already mentioned, the theory of combinatory spaces arose about 1974. Before 1980, parts of it have been presented in the papers Skordev [1975, 1976a-e, 1977, 1978, 1979] and Ivanov [1978] (in the paper Petrov and Skordev [1979] an attempt is made to use categories instead of semigroups, but the success is only partial). The state of this theory about the beginning of 1978 is presented in the monograph Skordev [1980]. During the time, when that book was in print, and later, many additions and improvements have been done (in particular, one of the conditions in the definition of the notion of combinatory space has been considerably weakened). A number of colleagues and students took an active part in the development of the theory and in its application since 1975. Here are the names of these people, listed in alphabetical order: A. Ditchev, N. Georgieva, O. Ignatov, L. Ivanov, R. Lukanova, S. Nikolova, E. Pazova, V. Petrov, I. Soskov, A. Soskova, M. Tabakov. Ideas from the theory have been used also in papers of G. Gargov, S. Passy, A. Radensky, T. Tinchev, D. Vakarelov and J. Zashev.
The present book is a completely new version of the above-mentioned monograph and aims at giving an account of the current state of the theory of combinatory spaces and of some of its applications. When starting the work on the manuscript, the author had rather ambitious plans. He planned to present not only his own results, but also those of his colleagues, and also to give a short account of the very interesting other algebraic generalizations of the theory of computability, obtained by L. Ivanov and J. Zashev. Unfortunately, the manuscript became too large. Therefore the author had to restrict his plans. The contributions of other authors are presented only partially in this book. As to Ivanov's and Zashev's generalizations (and especially Zashev's one), they are only mentioned with corresponding references (one of these references is the monograph Ivanov [1986], which contains also much information about combinatory spaces).
Some other reductions have been also made. Many results are given in the form of exercises (some of them are accompanied by hints). The details from Skordev [1980], concerning the possibility of using intuitionistic logic in most of the proofs, are omitted now. In the preface of that book, there was a brief survey of earlier publications to which the theory of combinatory spaces is more or less related. Now this survey is omitted, but the main list of references is supplemented with an additional bibliography, in whose first part those publications are listed (the second part is a list of publications later than 1980, which have a certain relationship to the theory of combinatory spaces, but are not mentioned in the text).
The author tried to avoid most references to his previous publications (especially to the previous version of this book). However, in some places such references are given to indicate additional sources of information or for making possible a discussion about the course of the development of the studies.
The main text of this book consists of three chapters and an appendix. All sections except those in the appendix, are accompanied by exercises. The exposition is organized in such a way, that results from the exercises are usually not logically needed in the other part of the text. An exception is made in Section III.8, where results from some exercises in Section II.1 are used. In Section 8 of the Appendix, some exercises from Sections II.4 and III.2 are needed not directly, but in the role of hints. The material from any of the sections III.6-III.9, as well as from any of the sections 3, 5, 7-10 of the Appendix, is not used in the further exposition.
For the reading of some places of the book, a knowledge of mathematical logic or recursive function theory is needed.
The help of many people and of some institutions was very essential for writing this book. Discussions with A. Ditchev, L. Ivanov, R. Lukanova, S. Nikolova, I. Soskov, A. Soskova, J. Zashev have been extremely useful for the work. I. Soskov and S. Nikolova helped also by reading some parts of the manuscript. L. Ivanov, I. Soskov and T. Tinchev introduced me to the text-editing by computer and gave me many practical advices in this respect. P. Petkov organized the printing of the text, A. Zinoviev did most of the printing, and V. Goranko provided me promptly with xerox copies. During this last month of the work, D. Vakarelov took my official duties upon himself in order to give me more free time. Throughout several months, my wife and my sons had to endure to see me at home only for staying overnight, and all this time they did everything in their power to assist me. The work on the manuscript has been partially supported by the Bulgarian Ministry of Science and Higher Education under Contract no. 247/1987, 1990. Kluwer Academic Publishers have been patient enough to wait for the manuscript much longer than it was initially planned.
I am deeply grateful to all these people and institutions.
| September, 1991 | Dimiter Skordev |