Understanding Computation

Computation Theory is a discipline that uses mathematical concepts and tools to expose the inherent nature of the activity which we call "computing". Why is it harder to perform some computations than other, apparently similar, ones? Are the differences in difficulty that we observe inherent, or are they artifacts of the way we specify and perform the computations of interest? Even more basically: How does one reason about such questions? This book strives to endow present and aspiring computation-oriented professionals with the conceptual and manipulative tools necessary to make Computation Theory part of their professional lives. In order to achieve this goal, the author employs three stratagems which set this book apart from most other texts. (i) He develops all needed mathematical concepts and tools from their simplest instances. The reader thereby has the opportunity to gain operational control over the underlying mathematics before using it. (ii) He organizes the development of the theory around clearly described "Pillars" and "Principles". Thereby, the reader sees computational topics that share intellectual origins developed in close physical proximity to one another. (iii) He strives to illustrate the "big ideas" that Computation Theory is built upon by applications of these ideas within applied (mostly computational) domains that readers have seen elsewhere in their reading and courses, in mathematics and in computational sciences that have evolved from mathematical infrastructures. If used as a text, the book is suitable for upper-level undergraduates and lower-level graduate students in mathematics, computer science, computational science, and computer engineering.