CS375: Automata, Formal Languages, and Computational Complexity

CS 375 Lecture Notes: "A Typical Reduction"

In class we saw several reductions from the universal language Lu to some other language L, to show that L was not decidable. We'll review the technique here. Actually, this is in essence a proof of Rice's theorem, but made specific here or there just for concreteness.

In each case, the reduction looked something like this:

In the above picture, the transformation A receives as input the description of a TM M, and an input word w, and A outputs the description of a machine TM,w such that (the description of) TM,w is in L if and only if M accepts w. Assuming such an algorithm A existed (and always halted), then the above machine is a decider for the universal language Lu, which is a contradiction, since we know Lu is not recursive. The conclusion is that the hypothesized decider ML for L cannot in fact exist, showing that L is not recursive.

In giving the details to such an argument in a particular case, it is necssary to show how to construct such a transformation A This is easiest to do in two steps:

  1. Describe how TM,w depends on M and w. That is, describe the TM TM,w, realizing that it is permissible for TM,w to include "hardcoded as data" in its state information, the description of M and of w.
  2. Describe how A can construct the description of TM,w, given the string w and the description of M. Note that A must necessarily hald for every input.

Lenny Pitt