CS 154 Class Handouts

• Languages.
• Minimization.
• Eliminating useless variables from context-free grammars.
• Decidability. And for the philosophically inclined students also definability, for comparison.
• Grammars.
• Rice's theorem.
• The undecidability of the empty intersection problem and the ambiguity problem for context-free grammars.
• Computable (or recursive) and partial recursive functions.
• Complexity classes.
• n-ary and n-adic representations of natural numbers.
• The undecidability of first order logic.
• The undecidability of arithmetic, Goedels incompleteness theorem, and the class of arithmetical languages.