Transcription
Computability and Complexity
Foundations of ComputingMichael Garey and Albert Meyer, editorsComplexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and OtherNetworks, Frank Thomson Leighton, 1983Equational Logic as a Programming Language, Michael J. O’Donnell, 1985General Theory of Deductive Systems and Its Applications, S. Yu Maslov, 1987Resource Allocation Problems: Algorithmic Approaches, Toshihide Ibaraki and Naoki Katoh,1988Algebraic Theory of Processes, Matthew Hennessy, 1988PX: A Computational Logic, Susumu Hayashi and Hiroshi Nakano, 1989The Stable Marriage Problem: Structure and Algorithms, Dan Gusfield and Robert Irving,1989Realistic Compiler Generation, Peter Lee, 1989Single-Layer Wire Routing and Compaction, F. Miller Maley, 1990Basic Category Theory for Computer Scientists, Benjamin C. Pierce, 1991Categories, Types, and Structures: An Introduction to Category Theory for the WorkingComputer Scientist, Andrea Asperti and Giuseppe Longo, 1991Semantics of Programming Languages: Structures and Techniques, Carl A. Gunter, 1992The Formal Semantics of Programming Languages: An Introduction, Glynn Winskel, 1993Hilbert’s Tenth Problem, Yuri V. Matiyasevich, 1993Exploring Interior-Point Linear Programming: Algorithms and Software, Ami Arbel, 1993Theoretical Aspects of Object-Oriented Programming: Types, Semantics, and Language Design,edited by Carl A. Gunter and John C. Mitchell, 1994From Logic to Logic Programming, Kees Doets, 1994The Structure of Typed Programming Languages, David A. Schmidt, 1994Logic and Information Flow, edited by Jan van Eijck and Albert Visser, 1994Circuit Complexity and Neural Networks, Ian Parberry, 1994Control Flow Semantics, Jaco de Bakker and Erik de Vink, 1996Algebraic Semantics of Imperative Programs, Joseph A. Goguen and Grant Malcolm, 1996Algorithmic Number Theory, Volume I: Efficient Algorithms, Eric Bach and Jeffrey Shallit,1996Foundations for Programming Languages, John C. Mitchell, 1996Computability and Complexity: From a Programming Perspective, Neil D. Jones, 1997
Computability and ComplexityFrom a Programming PerspectiveNeil D. JonesThe MIT PressCambridge, MassachusettsLondon, England
c 1997 Massachusetts Institute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by anyelectronic or mechanical means (including photocopying, recording, or informationstorage or retrieval) without permission in writing from the publisher.This book was set in Palatino by the author and was printed and bound in the UnitedStates of America.Library of Congress, Cataloging-in-Publication DataJones, Neil D.Computability and complexity: from a programming perspective / Neil D.Jones.p. cm. -- (Foundations of computing)Includes bibliographical references and index.ISBN 0-262-10064-9 (alk. paper)1. Electronic digital computers -- programming. 2. Computationalcomplexity.I. Title. II. Series.QA76.6.J6658 1997005.130 1--dc2196-44043CIP
ContentsSeries ForewordviiPrefaceIixToward the Theory11 Introduction32 The WHILE Language293 Programs as Data Objects47II65Introduction to Computability4 Self-interpretation: Universal Programs for WHILE and I675 Elements of Computability Theory736 Metaprogramming, Self-application, and Compiler Generation877 Other Sequential Models of Computation1118 Robustness of Computability1279 Computability by Functional Languages (partly by T. Æ. Mogensen) 13710 Some Natural Unsolvable ProblemsIIIOther Aspects of Computability Theory15316711 Hilbert’s Tenth Problem (by M. H. Sørensen)16912 Inference Systems and Gödel’s Incompleteness Theorem18913 Computability Theory Based on Numbers20714 More Abstract Approaches to Computability215v
vi ContentsIVIntroduction to Complexity23715 Overview of Complexity Theory23916 Measuring Time Usage24917 Time Usage of Tree-manipulating Programs26118 Robustness of Time-bounded Computation27119 Linear and Other Time Hierarchies for WHILE Programs28720 The Existence of Optimal Algorithms (by A. M. Ben-Amram)29921 Space-bounded Computations31722 Nondeterministic Computations33523 A Structure for Classifying the Complexity of Various Problems33924 Characterizations of logspace and ptime by GOTO Programs353VComplete Problems36725 Completeness and Reduction of One Problem to Another36926 Complete Problems for ptime38727 Complete Problems for nptime40128 Complete Problems for pspace409VIAppendix419A Mathematical Terminology and Concepts421Bibliography449Index460
Series ForewordTheoretical computer science has now undergone several decades of development. The“classical” topics of automata theory, formal languages, and computational complexityhave become firmly established, and their importance to other theoretical work and topractice is widely recognized. Stimulated by technological advances, theoreticians havebeen rapidly expanding the areas under study, and the time delay between theoretical progress and its practical impact has been decreasing dramatically. Much publicityhas been given recently to breakthroughs in cryptography and linear programming, andsteady progress is being made on programming language semantics, computational geometry, and efficient data structures. Newer, more speculative, areas of study includerelational databases, VLSI theory, and parallel and distributed computation. As this listof topics continues expanding, it is becoming more and more difficult to stay abreastof the progress that is being made and increasingly important that the most significantwork be distilled and communicated in a manner that will facilitate further research andapplication of this work. By publishing comprehensive books and specialized monographson the theoretical aspects of computer science, the series on Foundations of Computingprovides a forum in which important research topics can be presented in their entiretyand placed in perspective for researchers, students, and practitioners alike.Michael R. GareyAlbert R. Meyer
PrefaceThis book is a general introduction to computability and complexity theory. It shouldbe of interest to beginning programming language researchers who are interested in computability and complexity theory, or vice versa.The view from OlympusUnlike most fields within computer science, computability and complexity theory dealswith 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 wholecentury has quite precisely delineated the concepts and nature of effective procedures,and decidable and semi-decidable problems, and has established them to be essentiallyinvariant 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 problem’s input size), polynomial storage, computation with or without nondeterminism: theability 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” play a role analogousto channel capacity in engineering: No matter how clever a coding (in either sense of theword) is used, the bound cannot be overcome.Unfortunately, the field is well-known for impenetrable fundamental definitions,proofs of theorems, and even statements of theorems and definitions of problems. In myopinion this owes to some extent to the history of the field, and that a shift away fromthe Turing machine- and Gödel number-oriented classical approaches toward a greateruse of concepts familiar from programming languages will render classical computabilityand complexity results more accessible to the average computer scientist, and can makeits very strong theorems more visible and applicable to practical problems.This book covers classical models of computation and central results in computabilityand complexity theory. However, it differs from traditional texts in two respects:1. It is significantly more accessible, without sacrificing precision. This is achieved bypresenting the theory of computability and complexity using programming tech-
x Prefaceniques and motivated by programming language theory.12. It relieves some tensions long felt between certain results in complexity theory anddaily programming practice. A better fit is achieved by using a novel model ofcomputation, differing from traditional ones in certain crucial respects.Further, many of the sometimes baroque constructions of the classical theory becomemarkedly 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 looseway can be done more precisely and convincingly.The perspective of the bookFor those already familiar with computability and complexity theory, the two pointsabove can be somewhat elaborated.As for the first point, I introduce a simple imperative programming language calledWHILE, in essence a small subset of Pascal or LISP. The WHILE language seems to havejust the right mix of expressive power and simplicity. Expressive power is important whendealing with programs as data objects. The data structures of WHILE are particularlywell suited to this, since they avoid the need for nearly all the technically messy tasks ofassigning Gödel numbers to encode program texts and fragments (used in most if not allearlier texts), and of devising code to build and decompose Gödel numbers. Simplicity isalso essential to prove theorems about programs and their behavior. This rules out theuse of larger, more powerful languages, since proofs about them would be too complexto be easily understood.More generally, I maintain that each of the fields of computability and complexitytheory, and programming languages and semantics has much to offer the other. In theone direction, computability and complexity theory has a breadth, depth, and generalitynot often seen in programming languages, and a tradition for posing precisely definedand widely known open problems of community-wide interest. Also, questions concerningthe intrinsic impossibility or infeasibility of programs solving certain problems regardingprograms should be of interest to programming language researchers. For instance, manyproblems that turn up in the field of analysis and transformation of programs turn outto be undecidable or of intractably high complexity.1 Dana Scott was an early proponent of programming approach to automata [161], but it has not yetbeen widely used.
xiIn the other direction, the programming language community has a firm grasp ofalgorithm design, presentation and implementation, and several well-developed frameworks for making precise semantic concepts over a wide range of programming languageconcepts, e.g., functional, logic, and imperative programming, control operators, communication and concurrency, and object-orientation. Moreover programming languagesconstitute computation models some of which are more realistic in certain crucial aspectsthan traditional models.A concrete connection between computability and programming languages: the dryas-dust “s-m-n theorem” has been known in computability since the 1930s, but seemedonly a technical curiosity useful in certain proofs. Nonetheless, and to the surprise ofmany people, the s-m-n theorem has proven its worth under the alias partial evaluation orprogram specialization in practice over the past 20 years: when implemented efficiently,it can be used for realistic compiling, and when self-applied it can be used to generateprogram generators as well.Another cornerstone of computability, the “universal machine,” is nothing but a selfinterpreter, well-known in programming languages. Further, the “simulations” seen inintroductory computability and complexity texts are mostly achieved by informal compilers or, sometimes, interpreters.As for the second point above, a tension has long been felt between computabilityand complexity theory on the one hand, and “real computing” on the other. This is atleast in part bacause one of the first results proven in complexity is the Turing machinespeedup theorem, which asserts a counterintuitive (but true) fact: that any Turing machine program running in superlinear time can be replaced by another running twice asfast in the limit.2 The existence of efficient self-interpreters in programming languagetheory leads to the opposite result: a hierarchy theorem showing, for a more realisticcomputing model than the Turing machine, that constant time factors do matter. Moreprecisely, given time bound f (n), where n measures the size of a problem input, thereare problems solvable in time (1 ε)f (n) which cannot be solved in time f (n). Thusmultiplying the available computing time by a constant properly increases the class ofproblems that can be solved.This and other examples using programming language concepts lead (at least forcomputer scientists) to more understandable statements of theorems and proofs in computability and complexity, and to stronger results. Further new results include “intrinsic”characterizations of the well-known problem classes logspace and ptime on the basis2 The tension arises because the “trick” used for the Turing machine construction turns out to beuseless when attempting to speed up real computer programs.
xiiPrefaceof program syntax alone, without any externally imposed space or time bounds.Finally, a number of old computability and complexity questions take on new lifeand natural new questions arise. An important class of new questions (not yet fullyresolved) is: what is the effect of the programming styles we employ, i.e., functional style,imperative style, etc., on the efficiency of the programs we write?How to read this bookIf used as an introduction to computability (recursive function) theor
5 Elements of Computability Theory 73 6 Metaprogramming, Self-application, and Compiler Generation 87 7 Other Sequential Models of Computation 111 8 Robustness of Computability 127 9 Computability by Functional Languages (partly by T. Æ. Mogensen) 137 10 Some Natural Unsolvable Problems 153 III Other Aspects of Computability Theory 167 11 Hilbert’s Tenth Problem (by M. H. Sørensen) 169 12 .
