This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.
1. Decision problems
Consider a finite alphabet , and “words” on that alphabet (the “alphabet” may consist of digits, of abstract symbols, of actual letters, etc).
We use the notation to indicate the set of all “words” from the alphabet . Here, a word is simply a finite sequence of symbols from . For example, if is the usual alphabet, then
would be a word.
We are also given a set of words, and we say that the words in are valid. ( may be infinite.)
In the decision problem associated to , we are given as input a word in this alphabet. As output we say yes or no, depending on whether the word is in or not (i.e., whether it is “valid”).
We are interested in whether there is an algorithm that allows us to decide the right answer.