Egon Börger: Computability, Complexity, Logic.

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


To the towering achievement of the mathematics of the last one hundred years belongs the formulation of a precise, embracing concept of formal language and a general concept of algorithm.

Already Leibniz had recognised that the creation of a mathematically precise universal language for the expression of arbitrary statements (characteristica universalis) was related to the development of a sufficiently general (concept of) calculus (calculus ratiocinator) with regard to purely computable, formal - we would nowadays say algorithmic - decisions in scientific problems. To this corresponds the distinction, frequently made in linguistics, between descriptive and imperative elements or use of a language. Language or elements of a language can, on the one hand, be used for the description of states of affairs or facts, and on the other hand for the formulation and communication of directions (instructions) for the transformation (computation) of states of affairs and the construction (generation) of new states; such transformations include the solution of problems by the testing of objects for given properties (the so-called decision procedures).

Mathematics yields a classical example of this distinction with two basic types of mathematical problem formulation. One type of problem is to formulate statements about objects inside a mathematical language and prove them in a mathematical system (later formalised). The other is to specify instructions for computation or generation (enumeration) of objects within an algorithmic language. Thus, it can be proved that any two natural numbers have a greatest common divisor, or a procedure for generating the greatest common divisor can be developed. This example shows how close the connection between the descriptive and imperative elements of a language can be: to prove a mathematical sentence ALPHA from an axiom system Ax by means of the given rules R of a formal system, means to determine the truth-value of the sentence "ALPHA follows from Ax by means of R" by specifying how ALPHA is finally obtained from Ax by the formal transformations allowed in R. The proof of the sentence "To each x there exists a y with the property E" can consist of a specification of a procedure which, for arbitrary x, produces a y with the property E (that is, of the description of such a process including proof of its efficacy.)

Another representative example - a typical phenomenon for the development of algorithmic problem-solving methods - is the following: frequently, the main difficulty in the solution of a problem by computer program consists of circumscribing, bounding this problem exactly, excluding what is not intended to be part of the problem; this is what is commonly called "specifying" a problem. The efficiency of a programming language and the degree of correctness of the programs (describing algorithmic processes) formulated in it then depends essentially on the quality of the specification language as a vehicle of description and on the reliability of the methods by which programs are constructed from the specifications. The development of programming languages in the past thirty years shows very clearly that the descriptive and imperative use of language elements have an intrinsic connection; the kernel of the demands of the ever advancing programming language PROLOG rests on a single, flexible language, first order logic being simultaneously the specification- and the programming-language, on one and the same object able to be a statement (description of a problem in the domain of a logic-language) and a program (algorithm for the solution of this problem in the domain of a programming language.)

The present, already extensive mathematical theory of the concepts of algorithm and formal (logic-) language has decisively influenced, conceptually and methodically, the development of the way in which one deals with programmable computing equipment, and this influence promises to increase rather than weaken in the future. From the conviction that a mathematical theory loses nothing in intellectual interest by helping one understand a part of reality, I have undertaken in this book to give an introduction to algorithm theory and logic, oriented to the requirements of computer science without abandoning valuable traditions of the history of thought or sacrificing mathematical merit.

The structure of the book is therefore as follows: the first book is devoted to the theory of algorithms, the second to logic. The theory of algorithms (also known as computability theory) in its modern form is, above all, the theory of the extent and complexity of classes of algorithms and the automata and machines that realise them. It answers such questions as: What is the meaning of "algorithm", "universal programming language", "programmable computing equipment"? (Ch. A) What are the principal, general limitations of algorithmic problem-solving methods and what role is played in this area by logical or algorithmic means of description? (Ch.B). How can the efficiency and variety of algorithms be ordered hierarchically according to criteria which characterise algorithms by the available resources or purely syntactically by their structure? (Ch. C)

The basic questions of the book on logic are correspondingly: Can mathematical precision be given to the idea of an assertion being true independently of its eventual meaning and only on the basis of its logical structure, and can such a logical concept of truth be characterised algorithmically? (Ch.D) Is there a general algorithmic form of mathematical deduction from given premises? (Ch.E) How are the universality of a logical language and the universality of a programming language related? What is the relation between the expressibility of a logical language and the range of algorithms represented in it? What is the connection between the syntactical logical complexity of expressions and the computation complexity of algorithms represented by them ? (Ch. F. )