Reduction Patterns: A Practical Tool for Proving Undecidability

In the mandatory undergraduate course on Theory of Computation, students get familiar with the limits of computation and learn to prove that certain languages are undecidable or even non-recognizable. For this purpose, Rice's theorem and reduction technique are used. The former is very general and highly abstract, so that students find it difficult to use it. The later is more tangible, but involves severe creative challenges related to the need of defining a close relationship between two different languages. We have identified a number of patterns that address a variety of typical reduction problems, and that help the students as a practical tool for solution of reduction exercises.