E-Book Content
Preface This book is a general introduction to computability and complexity theory . It should be of interest to beginning programming language researchers who are interested in computability and complexity theory, or vice versa. The view from Olympus Unlike most fields within computer science, computability and complexity theory deals with analysis as much as with synthesis and with some concepts of an apparently absolute nature. Work in logic and recursive function theory spanning nearly the whole century has quite precisely delineated the concepts and nature of effective procedures, and decidable and semi-decidable problems , and has established them to be essentially invariant with respect to the computational device or logical theory used. Surprisingly , a few similarly invariant concepts have also arisen with respect to computations within bounded resources: polynomial time (as a function of a decision prob ' lem s input size), polynomial storage, computation with or without nondeterminism : the ability to " guess," and computation with " read- only " data access. Computability and complexity theory is, and should be, of central concern for practitioners as well as theorists. For example, " lower complexity bounds " playa role analogous to channel capacity in engineering : No matter how clever a coding (in either sense of the word ) is used, the bound cannot be overcome. Unfortunately , the field is well -known for impenetrability of fundamental definitions , proofs of theorems, and even statements of theorems and definitions of problems . thesis is that this owes to some extent to the history of the field , and that a shift away My from the Turing machine- and GOdel number -oriented classical approaches toward a greater use of concepts familiar from programming languages will render classical computability and complexity results more accessibleto the average computer scientist, and can make its very strong theorems more visible and applicable to practical problems . This book covers classical models of computation and central results in computability and complexity theory . However , it aims to differ from traditional texts in two respects :
Tobe significantly more accessible , without sacrificingprecision. This is achieved the of theory computability and complexity using programming by presenting
1 techniques and motivated by programming language theory . To relieve some tensions long felt between certain results in complexity theory and daily programming practice . A better fit is achieved by using a novel model of computation , differing from traditional ones in certain crucial respects. Further , many of the sometimes baroque constructions of the classical theory become markedly simpler in a programming context, and sometimes even lead to stronger theorems . A side effect is that many constructions that are normally only sketched in a loose way can be done more precisely and convincingly . The perspective
of the book
For those already familiar with computability and complexity theory, the two points above can be somewhat elaborated. As for the first point , I introduce a simple programming language called WHILE, in essencea small subset of Pascal or LISP. The WHILE language seems to have just the right mix of expressive power and simplicity . Expressivepower is important when dealing with programs as data objects. The data structures of WHILE are particularly well suited to this , since they avoid the need for nearly all the technically messy tasks of assigning COdelnumbersto encode program texts and fragments (used in most if not all earlier texts), and of devising code to build and decompose GOdel numbers. Simplicity is also essential to prove theorems about programs and their behavior . This rules out the use of larger, more powerful languages, since proofs about them would be too complex to be easily und