Yes/no questions are “enough”.
The bulk of computational theory deals with the analysis of decision problems, better known to the rest of the world as yes/no questions. I give you some arbitrary input; you give back a decision, either “yes” or “no”.
When I first started learning computational theory I felt like our almost exclusive discussion of yes/no questions was silly. After the Church-Turing Thesis it felt like a cop-out. We just asserted these things can do anything and you’re worrying about yes/no questions? We should be flying to the moon, solving bizarre mathematical formula, drawing pretty pictures, even giving short answers, anything more interesting than “yes” and “no”!
When I raised this concern, my teacherI think it was Cory Barker that semester. pointed out something that made me feel rather silly. “Just pose a series of decision problems,” he said, like a game of 20 questions. Assuming you want a finite-size answer you can find the answer pretty quickly using just yes’s and no’s.
As a concrete example, consider the following pattern of questions for getting textual information.
In practice, computational theory doesn’t propose actually asking six questions for each letter of each answer; when longer answers are needed abstractions for providing them are supplied. But a lot of theory finds thinking about decision problems is enough to characterize the kinds of theorems we hope to prove.
A large portion of computational theory makes decision problems concrete with the notions of languages, alphabets, tapes, and machines. An alphabet is a finite set of symbols. A language is a set of sequences of symbols from an alphabet. A tape is a sequence of symbols written down in a line. A machine is some device that accepts a tape to process and either accepts the input, rejects the input, or runs forever. The set of inputs a machine accepts is called the language the machine recognizes. Every decision problem can be viewed as a language recognition problem.
Don’t worry too much about those terms. I’ll define any examples I use in their respective posts.
As we delve deeper into theory we’ll be asking questions like “If we make a machine like this, what languages can it recognize?” These questions will take us through the “Chomsky hierarchy”. We’ll also ask questions like “are there languages no machine can recognize?” and “is it harder to recognize this language than that one?” Along the way we’ll skim over many of the interesting theoretical questions in computing.
Looking for comments…