Egon Börger: Computability, Complexity, Logic.
Studies in Logic and the Foundations of Mathematics, vol. 128,
North-Holland, Amsterdam 1989, pp. XX+592.
INTRODUCTION
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. )