6 I.Preliminaries People have been known to ask:"What really is computer science?Why don't we have submarine science,dishwasher science,or telephone science?"Telephones and dishwashers,it might be argued,are as important to modern life as computers are; perhaps more so.A slightly more focussed question is whether computer science is subsumed by such classical disciplines as mathematics,physics,neuro-science, electrical engineering,linguistics,logic,and philosophy. This book does not attempt to answer these questions.It is hoped,however,that the book will implicitly convey something of the uniqueness and universality of algorithmics,and hence something of the importance of computer science as an autonomous-albeit,young-field of study.Since computers could conceivably re- strict the generality of algorithmics,some people view the unavoidable link between the two as unfortunate.In fact,terming the field "computer science,"someone once said,is like referring to surgery as"knife science."Be that as it may,it is clear that algorithmics would never have developed the way it has without that link.However, it is generally agreed that the term"computer science"is misleading,and that some- thing like"information science,”“process science,.”or“the science of the discrete' might be better.Again,we only claim that our subject matter,algorithmics,forms the underpinnings of computer science,not that it replaces it. Some of the topics we discuss in the sequel,such as the existence of problems that computers cannot solve,have philosophical implications,not only on the limits of the wonderful machines we are able to build,but also on our own limits as mortals with finite mass and a finite life span.The profound nature of such implications notwithstanding,the emphasis in this book is on the more pragmatic goal of acquiring a deep understanding of the fundamentals of machine-executable processes,and the recipes,or algorithms,that govern them Some History Let us now review several important milestones in the development of computers and computer science,mainly to illustrate that as an orderly scientific discipline the field is extremely young. Somewhere between 400 and 300 B.C.,the great Greek mathematician Euclid invented an algorithm for finding the greatest common divisor(gcd)of two positive integers.The gcd of X and Y is the largest integer that exactly divides both X and Y.For example,the gcd of 80 and 32 is 16.The details of the algorithm itself are of no concern here,but the Euclidian algorithm,as it is called,is considered to be the first non-trivial algorithm ever devised. The word algorithm is derived from the name of the Persian mathematician Mohammed al-Khowarizmi,who lived during the ninth century,and who is cred- ited with providing the step-by-step rules for adding,subtracting,multiplying,and dividing ordinary decimal numbers.When written in Latin,the name became Algo- rismus,from which algorithm is but a small step.Clearly,Euclid and al-Khowarizmi were algorithmicians par excellence. Turning from software to hardware,one of the earliest machines to carry out a pro- cess controlled by what might be called an algorithm was a weaving loom inventedP1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 6 I. Preliminaries People have been known to ask: “What really is computer science? Why don’t we have submarine science, dishwasher science, or telephone science?” Telephones and dishwashers, it might be argued, are as important to modern life as computers are; perhaps more so. A slightly more focussed question is whether computer science is subsumed by such classical disciplines as mathematics, physics, neuro-science, electrical engineering, linguistics, logic, and philosophy. This book does not attempt to answer these questions. It is hoped, however, that the book will implicitly convey something of the uniqueness and universality of algorithmics, and hence something of the importance of computer science as an autonomous—albeit, young—field of study. Since computers could conceivably re￾strict the generality of algorithmics, some people view the unavoidable link between the two as unfortunate. In fact, terming the field “computer science,” someone once said, is like referring to surgery as “knife science.” Be that as it may, it is clear that algorithmics would never have developed the way it has without that link. However, it is generally agreed that the term “computer science” is misleading, and that some￾thing like “information science,” “process science,” or “the science of the discrete” might be better. Again, we only claim that our subject matter, algorithmics, forms the underpinnings of computer science, not that it replaces it. Some of the topics we discuss in the sequel, such as the existence of problems that computers cannot solve, have philosophical implications, not only on the limits of the wonderful machines we are able to build, but also on our own limits as mortals with finite mass and a finite life span. The profound nature of such implications notwithstanding, the emphasis in this book is on the more pragmatic goal of acquiring a deep understanding of the fundamentals of machine-executable processes, and the recipes, or algorithms, that govern them. ■ ■ ■ Some History Let us now review several important milestones in the development of computers and computer science, mainly to illustrate that as an orderly scientific discipline the field is extremely young. Somewhere between 400 and 300 B.C., the great Greek mathematician Euclid invented an algorithm for finding the greatest common divisor (gcd) of two positive integers. The gcd of X and Y is the largest integer that exactly divides both X and Y . For example, the gcd of 80 and 32 is 16. The details of the algorithm itself are of no concern here, but the Euclidian algorithm, as it is called, is considered to be the first non-trivial algorithm ever devised. The word algorithm is derived from the name of the Persian mathematician Mohammed al-Khowarizm ˆ ˆı, who lived during the ninth century, and who is cred￾ited with providing the step-by-step rules for adding, subtracting, multiplying, and dividing ordinary decimal numbers. When written in Latin, the name became Algo￾rismus, from which algorithm is but a small step. Clearly, Euclid and al-Khowarizm ˆ ˆı were algorithmicians par excellence. Turning from software to hardware, one of the earliest machines to carry out a pro￾cess controlled by what might be called an algorithm was a weaving loom invented