What Is A Computer and What Can It Do?
An Algorithms-Oriented Introduction to the Theory of Computation

Thomas C. O'Connell

College Publications


I took a bus home from the airport one morning a long time ago. After I sat down, a scary looking guy got on the bus, came up to my seat, and in a somewhat less than pleasant voice said, “You look like one of them POT smokers.” Simultaneously searching for a response and for something large and heavy with which to defend myself, I replied, “Nope.”

Scary Dude:
"You sure you're not one of them POT smokers?"

Unconvinced, he walked to the other end of the bus while I began to reconsider my decision not to join a martial arts class with a friend the week before. Scary Dude sat next to a student from the University of Texas. The student was reading a book for a literature class. Scary Dude asked, “What ya readin?” I couldn’t hear much of the reply. For some reason, I mostly heard Scary Dude’s part of the conversation. Then he said, “I read a book once, and it was Charlotte’s Web.”

Most of the computer science students I have taught are a lot like the scary dude on the bus – they don’t read. At least, they don’t read their textbooks. I can sympathize with them. Even with good books, I find myself getting too bogged down in the details and losing the story. I am hoping this book will be more like Charlotte’s Web. Not that I expect this to be an easy read or for it to include any pigs or spiders, but I want to stick to the story even if that means skipping over some details …and if I can figure out how to include a pig and a spider, I will. With that in mind, I intend to keep the main part of the book short. I do plan, however, to include a number of solved problems that would likely appear as theorems and examples in other books. Some of these problems will be much harder than others. Even if a problem seems incredibly difficult, at least think about the approach you would take in solving it before looking at the solution in the book.

Instructors using this book for a course may wish to use supplemental material to explore some topics more deeply. The book may be particularly useful for independent study, especially when the goal is to quickly develop an understanding of the central topics in the theory of computation. I would certainly not recommend using it to defend yourself on the bus ride home from the airport. Other, more comprehensive, computer science texts are much better suited for that purpose.

Thomas C. O’Connell
Skidmore College
Saratoga Springs, NY
October 2013