You are about to embark on the study of a fascinating and important subject: the
theory of computation. It comprises the fundamental mathematical properties of
computer hardware, software, and certain applications thereof. In studying this
subject we seek to determine what can and cannot be computed, how quickly,
with how much memory, and on which type of computational model. The subject
has obvious connections with engineering practice, and, as in many sciences, it
also has purely philosophical aspects.
I know that many of you are looking forward to studying this material but some
may not be here out of choice. You may want to obtain a degree in computer sci-
ence or engineering, and a course in theory is required—God knows why. After
all, isn't theory arcane, boring, and worst of all, irrelevant?
To see that theory is neither arcane nor boring, but instead quite understand-
able and even interesting, read on. Theoretical computer science does have many
fascinating big ideas, but it also has many small and sometimes dull details that
can be tiresome. Learning any new subject is hard work, but it becomes easier
and more enjoyable if the subject is properly presented. My primary objective in
writing this book is to expose you to the genuinely exciting aspects of computer
theory, without getting bogged down in the drudgery. Of course, the only way
to determine whether theory interests you is to try learning it.