Egon Börger: Computability, Complexity, Logic.

Studies in Logic and the Foundations of Mathematics, vol. 128, North-Holland, Amsterdam 1989, pp. XX+592.


This book is dedicated to
To both of them I owe more than this book - its beginning, its being completed and the best of its contents. I owe them, in particular, their example: it consists in confronting persons and situations in life and science selflessly and with an open mind, and never abandoning the purpose of recognising what is essential and true and to think and act accordingly.


The theme of this book is a pair of concepts, already recognised as belonging together by Leibniz, whose mathematical development from Frege to Turing has laid the theoretical foundation of computer science: the concept of formal language as carrier of the precise expression of meaning, facts, problems, and the concept of algorithm or calculus, that is, formally operating procedure for the solution of precisely described questions and problems. The book gives a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, the theory of formal languages and complexity theory. Apart from considering the fundamental themes, and nowadays classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory.

The aim of this book is twofold: to be a textbook for introductory courses in the above-mentioned disciplines as they occur in almost all current curricula of computer science, logic and mathematics, but apart from this, to be a monograph in which further results of new research (to a large extent in textbook form for the first time) are systematically presented and where the attempt is made to make explicit the connections and analogies between a variety of concepts and constructions. A price must be paid by the reader for the knowledge I expect him to acquire when and if the experiment is successful: for the beginner the first lectures of the text will be difficult due to the profusion of concepts, remarks and forward and backward references to currently posed clusters of problems particularly if he approaches the material by self-study unaccompanied by lectures. My advice is to initially skip over those parts which, despite study, are not understood; the connections will spring to mind on second reading.

The following remarks on the use of the book might be helpful; I have employed all parts of this book as the basis of introductory or advanced lectures on the foundations of theoretical computer science, automata theory and formal language, logic, computability- and complexity-theory. To enable the reader to recognise the use and interdependence of the various parts I have devised a detailed table of contents and a graph of interdependence. The sections marked with * contain material which is not treated in the basic courses but is suitable to follow them.

The arrangement of propositions as theorem, lemma, remark and exercise mirrors the methodical significance of the various states of affairs from a contemporary point of view. It says nothing about historical or individual achievements to have proved these propositions for the first time. Many a significant proposition becomes a simple example as a result of later progress.

I strongly recommend beginners to work out with pencil and paper, at first reading, all matters of routine or intermediate steps which are not explained in detail and to solve the exercises, or at least, try to solve them. By doing this one not only learns whether one has really understood the preceding subject matter and how to apply it, but one also acquires a feeling for what is essential in the techniques used. In this endeavour it might help that I have tried to express complicated ideas occurring in proofs without the use of formulas. The reader is advised to use this method of intuitive, but precise substantive thinking which opens the way to a deeper understanding.

The references to literature at the end of each section are considered as completions or those references given in the text.

I would like to express my heart-felt thanks to the many persons who have helped with the work on this book in the past years, by no means all of whom I am able to mention. I name in particular the following colleagues and collaborators who read the manuscript in whole or in part and who have given me valuable criticisms: K. Ambos-Spies, H. Braemik, t. Brand, A. Brueggemann, H. Fleischhack, J. Flum, G. Hensel, H. Kleine Buening, U. Loewen, L. Mancini, K. May, W. Roedding, H. Schwichtenberg, D. Spreen, J. Stoltefub, R. Verbeek, S. Wainer.

Separately I would like to thank: K.Ambos-Spies, whose elaboration of one of my Dortmund logic lectures I have partially used in chapters D/E, and who has given valuable help, particularly to BII3; U. Loewen for a critical reading of the entire manuscript and the preparation of the symbol- and subject-indices; K.May for careful corrections and numerous drawings; H.W.Roedding for the intricate control of the bibliography.

I would especially like to thank U. Minning, R. Kuehn, J. Kossmann, P. Schoppe and K. Grulich for the precise transposition of parts of several versions of my manuscript into the type-script for the printer. U. Minning has borne the main burden in this - her engaging and friendly manner has often allowed me to forget this arduous labour.

Finally, but not less heartily, I thank Walburga Roedding and many other colleagues who, in the past difficult six weeks, have given me their spontaneous moral support, thereby decisively helping me to complete this book.

Dortmund, 3.7. 1985 EGON BOERGER.

Note on the second edition. At this point I would like to express heartfelt thanks to M.Kummer, P. Paeppinghaus, V. Sperschneider: mainly because of their list of errors corrections have been made in the second edition. At this point also I thank ln advance all those readers who show me further errors.

Pisa, Spring 1986 EGON BOERGER.