This book looks at the most complex machine ever created--the computer--and at the even more complex programs that those machines execute. In a sense, though, it is complexity itself, rather than the machines and programs, that is the book's real subject. The methods for creating and understanding such complexity are at the core of the field known as computer science and are the major lesson you will take away from what you read here.
As an introduction to computer science, The Most Complex Machine is a bit unusual, in that it does not follow either of the two most common patterns for such an introduction. It is not designed to teach you to program, nor does it seek to make you an expert computer user. Instead, it attempts to introduce you to the fundamental ideas and principles on which the field is built. It was written to be used in a survey course directed mainly to students not currently majoring in computer science. It provides an overview of the field that is appropriate for such students whether or not they continue their study of computer science.
This book might also be used as a supplement in a first course in programming, to broaden student's exposure to the ideas of computer science. It might even make a good required introduction to the major, particularly for students with little previous experience with computer science. Finally, it should also be useful to the individual reader who wants to understand something of what really goes on inside a computer.
There are very few prerequisites for reading The Most Complex Machine. I do assume that you have some familiarity with computers, and it would certainly be useful for you to have had some experience using a computer. But all you really need to know is that a computer is a machine that can run programs. A program is a set of instructions for a computer to execute; you can make a computer do a wide variety of different things by giving it different programs. Even if you are fuzzy on these basic ideas, they should become clear to you as you read.
Some of the discussion in the book is mathematical; some of it is rather technical. But I try to cover everything at a level that can be followed with very little previous mathematical or technical experience--at least if you are willing to do some careful reading and thinking.
The first chapter, titled "What Computers Do," is really an introduction to the subject of complexity. This chapter is fundamental, in that it introduces many of the ideas that are covered more fully in the rest of the book. So, while you don't need to understand everything in this chapter in detail the first time through, you should pay close attention to the main ideas.
The next two chapters explain how computers can be built, step-by-step, out of very simple components. By the end of chapter 3, you will understand how a physical object can be built to execute an arbitrarily complex set of program instructions. This is the most technical part of the book. If you decide to skip over it, you will not be at a great disadvantage in the rest of the text. However, you will miss some really neat ideas, and I encourage you to browse through Section 2.1 and the beginnings of Sections 3.1 and 3.3 at least. And of course, you can read the chapter summaries.
Chapter 4, on "Theoretical Computers," shows that all computers, from the simple model computer constructed in Chapter 3 to the most advanced supercomputer, are really equally powerful except for their speed and the amount of memory they have. Furthermore, they are all subject to certain surprising limitations on the problems they can solve. The idea of "computational universality," covered in Section 4.1, is quite important; the rest of the chapter is interesting but not vital to later chapters.
The next chapter turns for the first time to real computers. It surveys their history, examines their social impact and discusses how practical machines differ from the simplified model computers considered in the previous chapters.
Chapters 6, 7, and 8 cover computer programming. Chapter 6 introduces the basic concepts, such as variables, loops, and decisions. Chapter 7 concentrates on methods for writing very large or complex programs. And Chapter 8 finishes by looking at some of the many different languages available for writing programs.
The last section of the book, Chapters 9 through 12, deals with applications of computing. After a general survey of applications in Chapter 9, the next three chapters cover three of the most important and exciting areas of computer science: computer graphics, parallel and distributed processing, and artificial intelligence. These four chapters can be read in any order.
* * *
The book is supplemented with a set of computer programs and with lab worksheets based on those programs. The programs are currently available only for Macintosh computers, but I am working to make them available to run under Windows as well. The programs are closely tied to the ideas covered in the text. They are not essential to understanding the material in the book, but the hands-on experience they give could certainly help to make some of the ideas presented here more accessible. (They are also, as far as I can judge them myself, rather fun.) The programs include:
The programs and the lab worksheets are available free on the Internet for personal, private use, and they can be freely used in courses that have adopted The Most Complex Machine as a textbook. I stipulate that they cannot be used in other courses. You should be able to find the programs in standard Macintosh FTP sites and bulletin boards. If you have access to the World Wide Web, you can get more information at the URL: http://math.hws.edu/TMCM.html. My electronic mail address is email@example.com. I can also be reached by regular mail at the address: David Eck, Department of Mathematics and Computer Science, Hobart and William Smith Colleges, Geneva NY 14456. I encourage comments, questions and general communication (but do not guarantee a response to every message I receive).
* * *
The chapters of the book are divided into numbered sections, which are in turn divided into subsections. When I refer to "Subsection 3.2.4," I mean the fourth subsection of the second section in Chapter 3. If I refer simply to "Section 2," I mean the second section in the current chapter. Figures are also numbered within chapters, so that "Figure 3.7" means the seventh figure in Chapter 3.
There is an annotated bibliography at the end of the book. Bibliographic references within the text are indicated by the author's name enclosed in brackets, with a page number if appropriate. For example, [Eck, p. 42] would refer to page 42 of a book in the bibliography by someone whose last name is Eck.
Each chapter ends with a set of questions. Almost all of the questions are meant to be thought-provoking and to require more than short, straightforward answers. The questions are part of the book and are meant to be read and pondered. My answers to most of the questions can be found in the last section of the book. You should read these answers--after thinking about the questions on your own--since they often provide more perspective on the ideas covered in the chapter itself.
* * *
I gratefully acknowledge the help and the encouragement of Kevin Mitchell and Richard Palais, who read large parts of this book when it was less readable than it is now and whose comments have certainly made it a better book than it would have been otherwise. (And you should obviously assume that any parts you don't like are among the parts they didn't get to read in advance.) I would also like to thank the copyeditor, Seth Maislin, and the people at A K Peters Ltd: Joni McDonald, Alexandra Benis, and Klaus Peters.