Prentice-Hall Series in Automatic Computation George Forsythe, editor BATES AND DOUGLAS, Programming Language/ One BALJMANN, FELICIANO, BAUER, AND SAMELSON, Introduction to ALGOL BOWLES (editor), Computers t`n Humanistic Research CESCHINO AND KUNTZMAN, Numerical Solution oflnitial Value Problems DESMONDE, Computers and Their Uses DESMONDE, Real- Time Data Processing S ystems: Introductory Concepts EVANS, WALLACE, AND SUTHERLAND, Simulation Us1`ng Digital Computers FORSYTHE AND MOLER, Computer Solution of Linear Algebraic Systems GOLDEN, Fortran IV: Programming and Computing GOLDEN AND LEICHUS, IBM 360; Programming and Computing HARTMANIS AND STEARNS, Algebraic Structure Theory ofSequential Machines HULL, Introduction to Computing MARTIN, Design of Real-time Computer Systems MARTIN, Programming Real- Time Computer Systems MINSKY, Computation: Finite and Infinite Machines MOORE, Interval Analysis SCHULTZ, Digital Processing: A System Orientation SNYDER, Chebyshev Methods in Numerical Approximation STROUD AND SECREST, Gaussian Quadrature Formulas TRAUB, Iterative Methods for the Solution of Equations VARGA, Matrix Iterative Analysis WILKINSON, Rounding Errors in Algebraic Processes ZIEGLE R, Shared- Tinte Data Processing PRENTICE HALL INTERNATIONAL, INC., London PRENTICE HALL OF AUSTRALIA, PTY. LTD.,Sydney PRENTICE HALL or CANADA, LTD., Toronto PRENTICE HALL OF INDIA PRIVATE LTD., New Delhi PRENTKI HALL ot JAPAN, INC., Tokyo /COMPUTATION: FINITE AND INFINITE MACH|NE§ MARVIN L. |y\|Ns|<Y Professor of Electrical Engineering Massachusetts Institute of Technology UN|VERS|TY OF \¢‘v'.A. ILRARY PRENTICE-HALL, INC. ENGLEWOOD CLIFFS. N. J. Q 975d2 © 1967 by Prentice-Hall, lnc. Englewood Cliffs, N. J. All rights reserved. No part of this book may be reproduced in any form or by any means without permission in writing from the publisher. Current printing (last digit): I0 9 8 7 6 5 4 3 2 Library ol`Congress Catalog Card No. 67-|2342 Printed in the United States of`America In memory of HENRY MINSKY PREFACE INTRODUCTION Man has within a single generation found himself sharing the world with a strange new species: the computers and computer-like machines. Neither history, nor philosophy, nor common sense will tell us how these machines will affect us, for they do not do “work” as did machines of the Industrial Revolution. Instead ofdealing with materials or energy, we are told that they handle “control” and “information” and even “intellectual processes.” There are very few individuals today who doubt that the computer and its relatives are developing rapidly in capability and com­ plexity, and that these machines are destined to play important (though not as yet fully understood) roles in society’s future. Though only some of us deal directly with computers, all of us are falling under the shadow of their ever-growing sphere of infiuence, and thus we all need to under­ stand their capabilities and their limitations. It would indeed be reassuring to have a book that categorically and systematically described what all these machines can do and what they cannot do, giving sound theoretical or practical grounds for each judg­ ment. However, although some books have purported to do this, it cannot be done for the following reasons: a) Computer-like devices are utterly unlike anything which science has ever considered-we still lack the tools necessary to fully analyze, synthesize, or even think about them; and b) The methods discovered so far are effective in certain areas, but are developing much too rapidly to allow a useful interpretation and interpolation of results. The abstract theory-as described in this book­ tells us in no uncertain terms that the machines’ potential range is enor­ mous, and that its theoretical limitations are of the subtlest and most elusive sort. There is no reason to suppose machines have any limitations not shared by man. We nevertheless expect our findings to crystallize in the years ahead­ and we are confident that the ideas and the formal methods that fill this book will remain in the mainstream of that theory which is yet to come. vii viii PREFACE We know this is so for several reasons. a) The central concept of effective computability appears necessary, even inevitable, once one has grasped it. In a convergence of ideas rare in science and mathematics, all sorts of independent attempts to form a “Theory of Machines” have been swept in this direction; and b) The sheer simplicity of the theory’s foundation and the extraordinarily short path from this foundation to its logical and surprising conclusions give the theory a mathematical beauty that alone guarantees it a permanent place in computer theory. THE MAIN GOAL The main goal of this book is to introduce the student to the concept of ejeczive procedure-a technical idea that has crystallized only fairly recently but already promises to be as important to the practical culture of modern scientific life as were the ideas of geometry, calculus, or atoms. It is a vital intellectual tool for working with or trying to build models of intricate, complicated systems-be they minds or engineering systems. Its most obvious application is to computation and computers, but I believe it is equally valuable for clear thinking about biological, psycho­ logical, mathematical, and (especially) philosophical questions. This claim must seen impossibly pretentious, and I had better explain it: The theory of effectiveness is useful not only to prove things about complex systems, but is also necessary to prove things about proof itself l The overall strategy of the book is very simple. We will try to engage the concept of effective procedure from such a variety of contexts, for­ malisms, and viewpoints, that its character will become thoroughly under­ stood-in the sense that one can recognize it and adapt it, almost without thinking, wherever and whenever it is appropriate. This concept has so many different aspects that one cannot hope to know them all equally well. It appears unexpectedly in aspects of practical computation, lin­ guistic theories, and mathematical logic. We must know some of these aspects very thoroughly, and others at least casually, if we are to be able to sense its style of operation in new situations. Both the text and the problems are designed with this polyvalence in mind: we pursue a few lines much further than most, but all these approaches keep linking and intersecting to form a web of weirdly different but connecting threads. Most fortunately, the theory is almost entirely self-contained, so that it has no formal mathematical “prerequisites” beyond a reasonable high­ school algebra course. A superficial glance through these pages might give a bewildering impression of the use of many complex and technical formalisms, but this is most definitely not the case. The book is not written in the formalisms, it is merely about them, and one is neither required nor expected to ever have seen them before! PREFACE ix The book has also a second, more playful theme. The many-headed concept which we call effective compatability often appears in an especially potent form-the Universal machine or system. This character has an astonishing variety of secret hiding places which we keep trying to ferret out. It is easily found in the ponderous operation of a modern digital computer’s order-code, or the gross, redundant structure of a FORTRAN or ALGOL-like programming language. (It is not important, at least in this book, that you know what these are.) But it can also lurk within the tiny structure of a “computer” with two memory registers or two instruction-tapes (Chapter I4), or in the seemingly childish bead-Stringing primitives of a Post normal system (Chapter 13), or even in a machine that (almost) neither reads nor writes on its tapes. While there is not much practical use in finding these “minimal Universal systems” they support our main goal by making us aware of exactly what is essential rather than merely practical or convenient in the concept of computation. Perhaps even more important, we learn of many difTerent ways in which great complexity of behavior can arise from the interactions of simple devices, simple actions, simple descriptions, or simple concepts. We see also many different ways in which the same complex behavior can arise from what appear to be utterly different kinds of interactive systems. The reader is prepared for both of these explorations in Part I, which is a training expedition into a smaller but essential (and in many ways analogous) territory. Within the finite-state machine area there exists as wide a variety of appearances of its own indigenous “central concept” (we explore fewer of these, though) and almost as surprising an assembly of its own minimal hiding places. I wish I could have captured in the different approaches to the theory a sense of the different styles of thinking that lead the early explorersm Post, Church, Turing, Kleene, McCulloch, and the others-to approach the same problems with such difTerent (technically and esthetically) formal methods. The personalities are obscured because in my attempt to modernize, simplify, and unify the results I have removed the individual details of the original developments. It would be well worth one’s time perusing Davis’ (1965) collection just to gain additional personal con­ tact with the masters! MATHEMATICAL TECHNIQUES As we stated above, the book is largely self-contained, given enough high-school mathematics to know about functional notation (even this is reviewed in Chapter 7) and mathematical induction (reviewed in Chap­ ter 4). MIT freshmen and sophomores have encountered no difficulty with the material, and though they may be more sophisticated mathe­ X PREFACE matically than most college students, I cannot imagine any good science student or computer programmer having serious trouble. I can, however, imagine educators (even mathematicians who have not encountered ‘“re­ cursive function theory”) becoming suspicious and wondering whether I have somehow constructed a simplitied or diluted version of the theory by “leaving out the calculus.” Quite the contrary: the calculus was never in it! This really is a branch of mathematics that stems directly from non-numerical, logical foundations. Indeed, a number of research workers are currently attempting to bring together this theory with that of Newton and Leibniz; the resulting new subject (currentlycalled “re­ cursive analysis”) has barely gotten offto a start. It is worth a few words to try to explain why classical mathematical analysis plays such a small role here. In developing a Theory of Compu­ tation we are trying to deal with systems composed of a great many parts, or very intricate structures. Classical mathematical methods can do this only in very special situations, and their limitations are very serious. Classically, one is unable to cope with even a few simultaneous non-linear equations, to say nothing of a few dozen, or a few million. Now it is true that under certain special conditions mathematical analysis can “revive,” as it were, when the situation gets complex in such a way that the parts of the system can be treated as individually and independently random­ this is what happens in Statistical Thermodynamic theories. But it must be stated, explicitly and emphatically, that this is just what does not happen when, as in a computation system, the structure has a more or­ ganized, purposeful structure. The statistical analysis works beautifully for things like gases. It works for precious little else. There simply is no reason to suppose that as computations grow large, one will discover any­ thing non-trivial by trying to “average-out” the effects of many events. The effect of the “conditional” (see Chapter 10) is too strong to allow anything like a “conservation” concept to have a place in the theory. Fortunately, the systems of computation have other features that make possible some analysis, though of a very different kind. Instead of the statiszically defined events used in physics, we use logically-defined classes of computations or expressions. They are tied together, not by geometric or energetic properties, but by their relations to similar machines or simi­ lar definitions. We can use machine parts so simple and with such simple interactions that we can apply the utterly transparent Logic of Proposi­ tions, where for an equivalent actual physical machine we would have to solve hopelessly opaque analytic equations. Chapters l, 5, and I2 explain in detail how the problem is reduced until this kind of analysis can be made. One could even complain that the main results are obtained by a most deceptive sort of parlor trick: instead of trying to solve equations, we study their descriptions! It must be admitted that in the long run this PREFACE xi method avoids entirely too many problems, and we can be quite sure that the development of the Theory ofComputation, in the years to come, will be centered around the problem of how to back off a little from this sim­ plitication, without going all the way back. The trouble now is that we do too much in one step. AS A TEXT This book has the form ofa textbook, and I have used earlier versions of it at MIT for several years. Students specializing in computer-related studies can absorb most of the material in a one-term course, since anyone with computer-programming experience is already subconsciously primed with the essential concepts, and needs only to see them precisely formu­ lated. For them, or for students with some higher mathematics courses, I would be inclined to assign Part I as a reading exercise, have them work the problems, and begin “teaching” with Part II. In any case, I feel that the material of Part I ought to be integrated very early somewhere in every scientific or engineering curriculum; the material of Parts II. and III can come considerably later (with the exception of Computer Science students). This edition is also designed for independent reading outside the classroom, and that is why I have given substantial hints for solving most of the harder problems. THE PROBLEMS The reader is asked to solve a number of problems scattered through­ out the book. Only a few ofthese are routine: most of them point toward branches the theory could take, and a few of them are diflicult research problems. The emphasis is on the application of new concepts to new situations rather than on acquiring technical proficiency through drill and repetition. My view is that the best way to understand a new idea is to discover by oneself how to use it to solve one or two reasonably hard problems; the point can easily escape after a hundred simple exercises. Solving a hard problem once can make the ideas a part of one’s thinking resources. The reader is therefore enjoined not to turn too easily to the solutions; I10t unless a needed idea has not come for a day or so. Every such con­ Cession has a price-loss of the experience obtained by solving a new kind of problem. Besides, even if reading the solutions were enough to HCquire the ability to solve such problems (which it is not), one rarely finds a set of ideas which are at once so elegant and so accessible to