INTRODUCTION TO COMPUTER THEORY SECOND EDITION Daniel I. A. Cohen Hunter College City University of New York John Wiley & Sons, Inc. New York Chichester Brisbane Toronto Singapore Weinheim I Ulll 1111111111 B048if7~8 Au Professeur M.-P. Schiitzenberger comme un temoignage de profonde et aff ectueuse reconnaissance ACQUISITIONS EDITOR Regina Brooks MARKETING MANAGER Jay Kirsch During the preparation of this second edition Alonzo Church has SENIOR PRODUCTION EDITOR Tony VenGraitis passed away at the age o/92. As a mathematical logician he was a DESIGN SUPERVISOR Anne Marie Renzi MANUFACTURING MANAGER Mark Cirillo theoretician par excellence and preeminent in the development of ILLUSTRATION COORDINATOR Rosa Bryant Computer Theory. His students include Stephen C. Kleene who PRODUCTION MANAGEMENT J. Carey Publishing Service figures prominently in this book. When Alan Turing was working on the consequences and ramifications of his model of computation it This book was set in 10/12 Times Roman by Digitype and was to Godel and Church in Princeton that he went to study. I too printed and bound by Hamilton Printing. The cover was printed by Lehigh Press. was a student of Church's. He was aformative influence on my Recognizing the importance of preserving what has been written, it is a development-a blessed memory and a saintly man. policy of John Wiley & Sons, Inc. to have books of enduring value published in the United States printed on acid-free paper, and we exert our best efforts to that end. The paper in this book was manufactured by a mill whose forest management programs include sustained yield harvesting of its timberlands. Sustained yield harvesting principles ensure that the number of trees cut each year does not exceed the amount of new growth. Copyright © 1991, 1997, by John Wiley & Sons, Inc. All rights reserved. Published simultaneously in Canada. Reproduction or translation of any part of this work beyond that permitted by Sections 107 and 108 of the 1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests for permission or further information should be addressed to the Permissions Department, John Wiley & Sons, Inc. 0-471-13772-3 Printed in the United States of America 10 9 8 7 6 5 4 PR FACE TO THE FIRST EDITION It has become clear that some abstract Computer Theory should be included in the education of undergraduate Computer Science majors. Leaving aside the obvious worth of knowledge for its own sake, the terminology, nota tions, and techniques of Computer Theory are necessary in the teaching of courses on com puter design, Artificial Intelligence, the analysis of algorithms, and so forth. Of all the pro gramming skills undergraduate students learn, two of the most important are the abilities to recognize and manipulate context-free grammars and to understand the power of the recur sive interaction of parts of a procedure. Very little can be accomplished if each advanced course has to begin at the level of defining rules of production and derivations. Every inter esting career a student of Computer Science might pursue will make significant use of some aspects of the subject matter of this book. Yet we find today, that the subjects of Automata Theory, Formal Languages, and Turing machines are almost exclusively relegated to the very advanced student. Only textbooks de manding intense mathematical sophistication discuss these topics. Undergraduate Computer Science majors are unlikely to develop the familiarity with set theory, logic, and the facility with abstract manipulation early enough in their college careers to digest the material in the existing excellent but difficult texts. Bringing the level of sophistication to the exact point where it meets the expected prepa ration of the intended student population is the responsibility of every carefully prepared textbook. Of all the branches of Mathematics, Computer Science is one of the newest and most independent. Rigorous mathematical proofs of the most profound theorems in this sub ject can be constructed without the aid of Calculus, Number Theory, Algebra, or Topology. Some degree of understanding of the notion of proof is, of course, required, but the tech niques employed are so idiosyncratic to this subject that it is preferable to introduce them to the student from first principles. Characteristic methods, such as making accurate conclu sions from diagrams, analyzing graphs, or searching trees, are not tools with which a typical mathematics major is familiar. Hardly any students come prepared for the convoluted sur prise of the Halting Problem. These then are the goals of this textbook: ( 1) to introduce a student of Computer Science to the need for and the working of mathematical proof; (2) to develop facility with the concepts, notations, and techniques of the theories of Automata, Formal Languages, and Turing machines; and (3) to provide historical perspective on the creation of the computer with a profound understanding of some of its capabilities and limi tations. Basically, this book is written for students with no presumed background of any kind. Every mathematical concept used is introduced from scratch. Extensive ~xamples and vii viii Preface to the First Edition illustrations spell out everything in detail to avoid any possibility of confusion. The bright student is encouraged to read at whatever pace or depth seems appropriate. For their excellent care with this project I thank the staff at John Wiley & Sons: Richard J. Bonacci, acquisitions editor, and Lorraine F. Mellon, Eugene Patti, Elaine Rauschal, and Ruth Greif of the editorial and production staffs. Of the technical people who reviewed the manuscript I thank Martin Kaliski, Adrian Tang, Martin Davis, and especially H. P. Edmund son, whose comments were invaluable and Martin J. Smith whose splendid special support was dispositive. Rarely has an author had an assistant as enthusiastic, dedicated, knowledge able and meticulous as I was so fortunate to find in Mara Chibnik. Every aspect of this pro PREFACE ject from the classnotes to the page proofs benefited immeasurably from her scrutiny. Very little that is within these covers-except for the few mistakes inserted by mischievous Mar TO THE SECOND EDITION tians-does not bare the mark of her relentless precision and impeccable taste. Every large project is the result of the toil of the craftsmen and the sacrifice and forebearance of those they were forced to neglect. Rubies are beneath their worth. Daniel I. A. Cohen In the first edition I intentionally omitted some topics because their discussion and/or proof involved mathematics that I felt was hopelessly beyond the scope of my intended audience. Students have not gotten more mathematically sophisticated but I have figured out how to demystify some of these themes in a much simpler way with no loss of rigor. Along the way various proofs that used to be cumbersome have been somewhat streamlined, and some embarrassing errors have been unearthed and demolished. Undergraduate Computer Science majors generally do not speak the language of math ematical symbolism fluently, nor is it important at their level that they do more than try. The value of mathematical iconography is that it enables professionals to perform their research and communicate their results more efficiently. The symbolism is not a profound discovery in and of itself. It is at best a means, not an end. To those to whom it is opaque, it is a hin drance to understanding. When this happens it is mathematically dysfunctional and a peda gogical anathema. Anyone who believes that {j : 1 s j s n } is somehow more rigorous than { 1, 2, ... n I is misguided. He has forgotten how the typography "1 s j s n" was defined to him in the first place. All mathematical symbolism can be reduced to human language be cause it is through iterations of human language substitutes that it was defined initially. In stead of introducing "mathematics" in an alienating form that only has to be expounded any way, I prefer to skip the pretentious detour and provide the explanation itself directly. Computer science has needlessly carried an inferiority complex among the branches of mathematics, causing a defensive embedding into mainstream symbolism to lend it an aura of legitimacy. Yet it has been, as Hilbert himself predicted, one of the principal departments of mathematical discovery in the last century. Still no pretense is made to encyclopedic completeness. This textbook is an introduction to computer theory and contains the minimum collegiate requirements of theory for com puter science majors. No, I have not added a chapter on NP-completeness, primitive and par tial recursion, program verification, artificial intelligence, nor Renaissance architecture. These are all topics worthy of being included in some course but to squeeze them in here would necessarily displace some of the more pertinent and fundamental aspects of theory, and would thereby disadvantage the student. High on my list of cheap tricks is the inclusion of material in textbooks that is never meant to be covered in the intended course in the first place. I have heard members of text book selection committees who say, "Let's adopt X's elementary calculus text because he has a chapter on general relativity while our current textbook contains only cakulus." Sales manship should not be the business of textbook authors-educating students should. Mak- ix x Preface to the Second Edition ing students pay for 300 extra pages of material that is not intended to be covered in the course harms them in financial, muscular, and psychological ways. Ideally a textbook should begin at the level of understanding of the students taking the course. It should include all the material they have contracted to learn presented in a fashion maximally suited for them to absorb. When it has completed the syllabus it should stop. Al lowances may be made for instructor discretion in choosing material that is basic to the course and in the selection of which topics warrant special emphasis. However, there are some fanatics who have the grandiose notion that to be a great teacher is to stuff more mater CONTENTS ial into a course than their students can learn. I view this as sheer and simple breach of con tract. Let these zealots adopt a graduate textbook and let their students protest accordingly. There is no comparison between the error of covering too little and covering too much. To attempt to cover too much is to rob the students of the chance to learn and to undermine their self-confidence. This book is unabashedly easy to read. It is intentionally slow-paced and repetitive. Let PART I AUTOMATA THEORY the bright student blitz through it, but let the slower student find comfort and elucidation. The nuances in this material are unlike anything (mathematical or otherwise) seen before in {1 Background 2 a course or textbook. A leisurely stroll through these charming gems can be enjoyable, stim (2 Languages 7 ulating, and rewarding. My duty to computer science students is to protect them against their own fear of mathematics, to demonstrate to them that a proof is no more or less than an un Languages in the Abstract 7 derstanding of why the theorem is true, and to allow. them to savor the intellectual richness Introduction to Defining Languages 10 of the theoretical foundations of what is ultimately the most important invention since antiq Kleene Closure 14 uity. Problems 19 Is this book ideal? That would be unlikely, wouldn't it? But it is designed with good sci Recursive Definitions 21 entific intentions and sincere concern for those interested in learning. It gives me pleasure to thank Chanah Brenenson who served as the technical editor and A New Method for Defining Languages 21 tireless critic to this edition. May she live long and prosper. An Important Language: Arithemetic Expressions 25 Problems 28 DIAC Regular Expressions 31 Defining Languages by Another New Method 31 Formal Definition of Regular Expressions 35 Languages Associated with Regular Expressions 43 Finite Languages Are Regular 44 How Hard It Is To Understand a Regular Expression 45 Introducing EVEN-EVEN 48 Problems 49 Finite Automata 52 Yet Another Method for Defining Languages 52 FAs and Their Languages 59 EVEN-EVEN Revisited 69 Problems 71 6 Transition Graphs 76 Relaxing the Restriction on Inputs 76 Looking at TGs 81 Generalized Transition Graphs 86 Nondeterminism 87 Problems 88 xi x Preface to the Second Edition ing students pay for 300 extra pages of material that is not intended to be covered in the course harms them in financial, muscular, and psychological ways. Ideally a textbook should begin at the level of understanding of the students taking the course. It should include all the material they have contracted to learn presented in a fashion maximally suited for them to absorb. When it has completed the syllabus it should stop. Al lowances may be made for instructor discretion in choosing material that is basic to the course and in the selection of which topics warrant special emphasis. However, there are some fanatics who have the grandiose notion that to be a great teacher is to stuff more mater CONTENTS ial into a course than their students can learn. I view this as sheer and simple breach of con tract. Let these zealots adopt a graduate textbook and let their students protest accordingly. There is no comparison between the error of covering too little and covering too much. To attempt to cover too much is to rob the students of the chance to learn and to undermine their self-confidence. This book is unabashedly easy to read. It is intentionally slow-paced and repetitive. Let PART I AUTOMATA THEORY the bright student blitz through it, but let the slower student find comfort and elucidation. The nuances in this material are unlike anything (mathematical or otherwise) seen before in ( 1 Background 2 a course or textbook. A leisurely stroll through these charming gems can be enjoyable, stim (2 Languages 7 ulating, and rewarding. My duty to computer science students is to protect them against their own fear of mathematics, to demonstrate to them that a proof is no more or less than an mi Languages in the Abstract 7 derstanding of why the theorem is true, and to allow them to savor the intellectual richness Introduction to Defining Languages 1O of the theoretical foundations of what is ultimately the most important invention since antiq Kleene Closure 14 uity. Problems 19 Is this book ideal? That would be unlikely, wouldn't it? But it is designed with good sci 3} Recursive Definitions 21 entific intentions and sincere concern for those interested in learning. It gives me pleasure to thank Chanah Brenenson who served as the technical editor and A New Method for Defining Languages 21 tireless critic to this edition. May she live long and prosper. An Important Language: Arithemetic Expressions 25 Problems 28 DIAC Regular Expressions 31 Defining Languages by Another New Method 31 Formal Definition of Regular Expressions 35 Languages Associated with Regular Expressions 43 Finite Languages Are Regular 44 How Hard It Is To Understand a Regular Expression 45 Introducing EVEN-EVEN 48 Problems 49 Finite Automata 52 Yet Another Method for Defining Languages 52 FAs and Their Languages 59 EVEN-EVEN Revisited 69 Problems 71 6 Transition Graphs 76 Relaxing the Restriction on Inputs 76 Looking at TGs 81 Generalized Transition Graphs 86 Nondeterminism 87 Problems 88 xi xii Contents Contents xiii 7 Kleene's Theorem 92 · 14 Pushdown Automata 289 Unification 92 A New Format for FAs 289 Turning TGs into Regular Expressions 93 Adding a Pushdown Stack 293 Converting Regular Expressions into FAs 108 Defining the PDA 307 Nondeterministic Finite Automata 135 Problems 312 NFAs and Kleene's Theorem 140 15j CFG =PDA 318 Problems 142 Building a PDA for Every CFG 318 8 Finite Automata with Output 149 Building a CFO for Every PDA 327 Moore Machines 149 Problems 348 Mealy Machines 152 /16'; Non-Context-Free Languages 351 Moore Mealy 156 Transducers as Models of Sequential Circuits 161 Self-Embeddedness 351 Problems 164 The Pumping Lemma for CFLs 360 Problems 373 9 Regular Languages 169 17 Context-Free Languages 376 Closure Properties 169 Complements and Intersections 172 Closure Properties 376 Problems 185 Intersection and Complement 385 Mixing Context-Free and Regular Languages 393 JO Nonregular Languages 187 Problems 398 The Pumping Lemma 187 18 Decidability 402 The Myhill-Nerode Theorem 196 Quotient Languages 200 Emptiness and Uselessness 402 Problems 203 Finiteness 408 Membership- The CYK Algorithm 410 u· Decidability 207 Parsing Simple Arithmetic 415 Equivalence 207 Problems 429 Finiteness 214 Problems 217 .PART III TURING THEORY 19 Turing Machines 434 PART II PUSHDOWN AUTOMATA THEORY The Turing Machine 434 The Subprogram INSERT 449 12 Context-Free Grammars 224 The Subprogram DELETE 452 Syntax as a Method for Defining Languages 224 Problems 454 Symbolism for Generative Grammars 230 20 Post Machines 457 Trees 241 Lukasiewicz Notation 245 The Post Machine 457 Ambiguity 250 Simulating a PM on a TM 462 The Total Language Tree 252 Simulating a TM on a PM 468 Problems 254 Problems 4 77 13' Grammatical Format 259 21 Minsky's Theorem 480 Regular Grammars 259 The Two-Stack PDA 480 Killing A-Productions 265 Just Another TM 482 Killing Unit Productions 272 Problems 492 Chomsky Normal Form 275 22 Variations on the TM 494 Leftmost Derivations 282 Problems 285 The Move-in-State Machine 494 xiv Contents The Stay-Option Machine 499 PART I The k-Track TM 502 The Two-Way Infinite TAPEM odel 511 The Nondeterministic TM 518 The Read-Only TM 524 Problems 531 23 TM Languages 535 Recursively Enumerable Languages 535 The Encoding of Turing Machines 545 A Non-Recursively Enumerable Language 549 The Universal Turing Machine 552 Not All r.e. Languages Are Recursive 557 Decidability 558 Problems 562 24 The Chomsky Hierarchy 565 Phrase-Structure Grammars 565 Type0=TM 574 The Product and Kleene Closure of r.e. Languages 586 Context-Sensitive Grammars 588 Problems 590 25 Computers 594 Defining the Computer 594 Computable Functions 599 Church's Thesis 610 TMs as Language Generators 612 Problems 616 Bibliography 619 Theorem Index 621 Index 625 Automata Theory CHAPTER 1 Background 3 are unknown at the present time, but that such techniques will never exist in the future no CHAPTER 1 matter how many clever people spend millennia attempting to discover them. The nature of our discussion will be the frontiers of capability in an absolute and time less sense. This is the excitement of mathematics. The fact that the mathematical models that we create serve a practical purpose through their application to computer science, both in the development of structures and techniques necessary and useful to computer programming Background and in the engineering of computer architecture, means that we are privileged to be playing a game that is both fun and important to civilization at the same time. The term computer is practically never encountered in this book-we do not even de fine the term until the final pages. The way we shall be studying about computers is to build mathematical models, which we shall call machines, and then to study their limitations by analyzing the types of inputs on which they operate successfully. The collection of these successful inputs we shall call the language of the machine, by analogy to humans who can understand instructions given to them in one language but not another. Every time we intro duce a new machine we will learn its language, and every time we develop a new language we shall try to find a machine that corresponds to it. This interplay between languages and The twentieth century has been filled with the most incredible shocks and surprises: the the machines will be our way of investigating problems and their potential solution by auto ory of relativity, the rise and fall of communism, psychoanalysis, nuclear war, television, matic procedures, often called algorithms, which we shall describe in a little more detail moon walks, genetic engineering, and so on. As astounding as any of these is the advent of shortly. the computer and its development from a mere calculating device into what seems like a The history of the subject of computer theory is interesting. It was formed by fortunate "thinking machine." coincidences, involving several seemingly unrelated branches of intellectual endeavor. A The birth of the computer was not wholly independent of the other events of this cen small series of contemporaneous discoveries, by very dissimilar people, separately moti tury. Its inception was certainly impelled if not provoked by war and its development was fa vated, flowed together to become our subject. Until we have established more of a founda cilitated by the evolution of psycho-linguistics, and it has interacted symbiotically with all tion, we can only describe in general terms the different schools of thought that have melded the aforementioned upheavals. The history of the computer is a fascinating story; however, it into this field. is not the subject of this course. We are concerned instead with the theory of computers, The most fundamental component of computer theory is the theory of mathematical which means that we shall form several mathematical models that will describe with varying logic. As the twentieth century started, mathematics was facing a dilemma. Georg Cantor degrees of accuracy parts of computers, types of computers, and similar machines. The con had recently invented the theory of sets (unions, intersections, inclusion, cardinality, etc.). cept of a "mathematical model" is itself a very modern construct. It is, in the broadest sense, But at the same time he had discovered some very uncomfortable paradoxes-he created a game that describes some important real-world behavior. Unlike games that are simula things that looked like contradictions in what seemed to be rigorously proven mathematical tions and used for practice or simply for fun, mathematical models abstract, simplify, and theorems. Some of his unusual findings could be tolerated (such as the idea that infinity codify to the point that the subtle observations and conclusions that can be made about the comes in different sizes), but some could not (such as the notion that some set is bigger than game relate back in a meaningful way to the physical world, shedding light on that which the universal set). This left a cloud over mathematics that needed to be resolved. was not obvious before. We may assert that chess is a mathematical model for war, but it is a To some the obvious solution was to ignore the existence of set theory. Some others very poor model because wars are not really won by the simple assassination of the leader of thought that set theory had a disease that needed to be cured, but they were not quite sure the opposing country. where the trouble was. The naive notion of a general "set" seemed quite reasonable and in The adjective "mathematical" in this phrase does not necessarily mean that classical nocent. When Cantor provided sets with a mathematical notation, they should have become mathematical tools such as Euclidean geometry or calculus will be employed. Indeed, these mathematical objects capable of having theorems about them proven. All the theorems that areas are completely absent from the present volume. What is mathematical about the mod dealt with finite sets appeared to be unchallengeable, yet there were definite problems with els we shall be creating and analyzing is that the only conclusions that we shall be allowed the acceptability of infinite sets. In other branches of mathematics the leap from the finite to to draw are claims that can be supported by pure deductive reasoning; in other words, we are the infinite can be made without violating intuitive notions. Calculus is full of infinite sums obliged to prove the truth about whatever we discover. Most professions, even the sciences, that act much the way finite sums do; for example, if we have an infinite sum of infinitesi are composed of an accumulation of wisdom in the form of general principles and rules that mals that add up to 3, when we double each term, the total will be 6. The Euclidean notion usually work well in practice, such as "on such and such a wood we recommend this under that the whole is the sum of its parts-'seems to carry over to infinite sets as well; for example, coat," or "these symptoms typically respond to a course of medication X." This is com when the even integers are united with the odd integers, the result is the set of all integers. pletely opposite from the type of thing we are going to be doing. While most of the world is Yet, there was definitely an unsettling problem in that some of Cantor's "theorems" gave (correctly) preoccupied by the question of how best to do something, we shall be completely contradictory results. absorbed with the question of whether certain tasks can be done at all. Our main conclusions In the year 1900, David Hilbert, as the greatest living mathematician, was invited to ad will be of the form, "this can be done" or "this can never be done." When we reach conclu dress an international congress to predict what problems would be important in the century sions of the second type, we shall mean not just that techniques for performing these tasks to come. Either due to his influence alone, or as a result of his keen analysis, or as a tribute 2 4 CHAPTER 1 Background CHAPTER 1 Background 5 to his gift for prophecy, for the most part he was completely correct. The 23 areas he indi Church, Stephen Kleene, Emil Post, Andrei Andreevich Markov, John von Neumann, and cated in that speech have turned out to be the major thrust of mathematics for the twentieth Alan Turing, worked mostly independently and came up with an extraordinarily simple century. Although the invention of the computer itself was not one of his predictions, several set of building blocks that seemed to be the atoms from which all mathematical algo of his topics tum out to be of seminal importance to computer science. rithms can be comprised. They each fashioned various (but similar) versions of a univer First of all, he wanted the confusion in set theory resolved. He wanted a precise ax sal model for all algorithms-what, from our perspective, we would call a universal al iomatic system built for set theory that would parallel the one that Euclid had laid down for gorithm machine. Turing then went one step farther. He proved that there were geometry. In Euclid's classic texts, each true proposition is provided with a rigorous proof in mathematically definable fundamental questions about the machine itself that the ma which every line is either an axiom or follows from the axioms and previously proven theo chine could not answer. rems by a specified small set of rules of inference. Hilbert thought that such an axiom sys On the one hand, this theorem completely destroyed all hope of ever achieving any part tem and set of rules of inference could be developed to avo'id the paradoxes Cantor (and oth of Hilbert's program of mechanizing mathematics, or even of deciding which classes of ers) had found in set theory. problems had mechanical answers. On the other hand, Turing's theoretical model for an al Second, Hilbert was not merely satisfied that every provable result should be true; he gorithm machine employing a very simple set of mathematical structures held out the possi also presumed that every true result was provable. And even more significant, he wanted a bility that a physical model of Turing's idea could actually be constructed. If some human methodology that would show mathematicians how to find this proof. He had in his mind a could figure out an algorithm to solve a particular class of mathematical problem, then the specific model of what he wanted. machine could be told to follow the steps in the program and execute this exact sequence of In the nineteenth century, mathematicians had completely resolved the question of solv instructions on any inserted set of data (tirelessly and with complete precision). ing systems of linear equations. Given any algebraic problem having a specified number of The electronic discoveries that were needed for the implementation of such a device in linear equations, in a specified set of unknowns, with specified coefficients, a system had cluded vacuum tubes, which just coincidentally had been developed recently for engineering been developed (called linear algebra) that would guarantee one could decide weather the purposes completely unrelated to the possibility of building a calculating machine. This was equations had any simultaneous solution at all, and find the solutions if they did exist. another fortuitous phenomenon of this period of history. All that was required was the impe This would have been an even more satisfactory situation than existed in Euclidean tus for someone with a vast source of money to be motivated to invest in this highly specula geometry at the time. If we are presented with a correct Euclidean proposition relating line tive project. It is practically sacrilegious to maintain that World War II had a serendipitous segments and angles in a certain diagram, we have no guidance as to how to proceed to pro impact on civilization no matter how unintentional, yet it was exactly in this way that the duce a mathematically rigorous proof of its truth. We have to be creative-we may make first computer was born-sponsored by the Allied military to break the German secret code, false starts, we may get completely lost, frustrated, or angry. We may never find the proof, with Turing himself taking part in the construction of the machine. even if many simple, short proofs exist. Linear algebra guarantees that none of this will ever What started out as a mathematical theorem about mathematical theorems-an abstrac happen with equations. As long as we are tireless and precise in following the rules, we must tion about an abstraction-became the single most practically applied invention since the prevail, no matter how little imagination we ourselves possess. Notice how well this de wheel and axle. Not only was this an ironic twist of fate, but it all happened within the re scribes the nature of a computer. Today, we might rephrase Hilbert's request as a demand for markable span of 10 years. It was as incredible as if a mathematical proof of the existence of a set of computer programs to solve mathematical problems. When we input the problem, intelligent creatures in outer space were to provoke them to land immediately on Earth. the machine generates the proof. Independently of all the work being done in mathematical logic, other fields of science It was not easy for mathematicians to figure out how to follow Hilbert's plan. Math and social science were beginning to develop mathematical models to describe and analyze ematicians are usually in the business of creating the proofs themselves, not the proof-gener difficult problems of their own. As we have noted before, there is a natural correspondence ating techniques. What had to be invented was a whole field of mathematics that dealt with between the study of models of computation and the study of linguistics in an abstract and algorithms or procedures or programs (we use these words interchangeably). From this we mathematical sense. It is also natural to assume that the study of thinking and learning see that even before the first computer was ever built, some people were asking the question branches of psychology and neurology-play an important part in understanding and facili of what programs can be written. It was necessary to codify the universal language in which tating computer theory. What is again of singular novelty is the historical fact that, rather algorithms could be stated. Addition and circumscribing circles were certainly allowable than turning their attention to mathematical models to computerize their own applications, steps in an algorithm, but such activities as guessing and trying infinitely many possibilities their initial development of mathematical models for aspects of their own science directly at once were definitely prohibited. The language of algorithms that Hilbert required evolved aided the evolution of the computer itself. It seems that half the intellectual forces in the in a natural way into the language of computer programs. world were leading to the invention of the computer, while the other half were producing ap The road to studying algorithms was not a smooth one. The first bump occurred in 1931 plications that were desperate for its arrival. when Kurt Godel proved that there was no algorithm to provide proofs for all the true state Two neurophysiologists, Warren McCulloch and Walter Pitts, constructed a mathemati ments in mathematics. In fact, what he proved was even worse. He showed that either there cal model for the way in which sensory receptor organs in animals behave. The model they were some true statements in mathematics that had no proofs, in which case there were cer constructed for a "neural net" was a theoretical machine of the same nature as the one Turing tainly no algorithms that could provide these proofs, or else there were some false state invented, but with certain limitations. ments that did have proofs of their correctness, in which case the algorithm would be disas Modem linguists, some influenced by the prevalent trends in mathematical logic and trous. some by the emerging theories of developmental psychology, had been investigating a very Mathematicians then had to retreat to the question of what statements do nave proofs similar subject: What is language in general? How could primitive humans have developed ) and how can we generate these proofs? The people who worked on this problem, Alonzo language? How do people understand it? How do they learn it as children? What ideas can