Saturday, January 9, 2010

Show that L_min is not in coRE

So I taught the recursion theorem and showed (as in Sipser) that the language L_min, consting of all minimal Turing machine descriptions, is not recursively enumerable (RE). The argument goes like this: suppose to the contrary that L_min is in RE, with some enumerator E. Define the Turing machine B, which obtains its own description [B] via the recursion theorem, waits until E generates a program C that is longer than [B], and then simulates the behavior of C. The contradiction results from the assumption that E only generates minimal programs and the construction of B as a program that's shorter than some "minimal" program!

Now I want to show that L_min is not in coRE (meaning that its complement is not in RE). This has turned out to be quite a bit trickier, at least for me! I believe I have a proof, but I welcome solutions from the readers.

1 comment:

Aryeh said...

What I believed to be a proof has turned out to be wrong -- as I was writing it on the board! Good thing my students have patience...

A correct proof has turned out to be far more difficult than I had originally imagined; here it is, thanks to Ryan Williams and mathoverflow: