At the tail end of CS103, we talk about decidable and recognizable (R and RE) languages as a way of talking about problems that are beyond the capacity of computers to solve. I’ve typically framed the discussion of these languages in terms of trying to answer this overarching question:
What problems can be solved by a computer?
Since CS103 stresses mathematical rigor, I usually introduce this question less as a concrete mathematical goal and more as a framework for thinking about compution. In order to rigorously answer this question, we nee definitions of “problem,” “computer,” and “solve.” In formal language theory, problems are modeled by languages and computers are modeled by Turing machines. The idea of “solving” a problem can then be formulated in terms of decidability and recognizability, along with a ton of other solution strategies that we don’t explore in the course (e.g. co-recognizability).
To help students get why it’s so important to have a formal definition of what it means to solve a problem, I’ve added in this question to the problem set, which connect the earlier material on implications to the later material on computability:
Let be a language over and be a TM with input alphabet . Below are three properties that may hold for :
- halts on all inputs.
- For any string , if accepts , then .
- For any string , if rejects , then .
At some level, for a TM to claim to solve a problem, it should have at least some of these properties. Interestingly, though, just having two of these properties doesn’t say much.
- Prove that if is any language over , then there is a TM that satisfies properties (1) and (2).
- Prove that if is any language over , then there is a TM that satisfies properties (1) and (3).
- Prove that if is any language over , then there is a TM that satisfies properties (2) and (3).
- Suppose that is a language over for which there is a TM that satisfies properties (1), (2), and (3). What can you say about ? Prove it.
Many students, upon reading this problem, think that they must have misread something, since it looks like it suggests that all languages are decidable or something along those lines. Working out why exactly this isn’t the case is trickier and forces students to read the properties closely to determine what they mean.
These questions also segue nicely into questions about sound and complete approximations to problems. Many students ask whether, if a language is undecidable, there’s still a way to build a TM that gets the right answer “most of the time,” for some definition of “most of the time,” or that gets an “approximately” correct answer. This question shows that it’s always possible to find a decidable subset or superset of any given language (though not a particularly useful one), and is a great launching point for a further discussion of the topic.