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.
Subscribe to:
Post Comments (Atom)
1 comment:
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:
http://mathoverflow.net/questions/11566/a-proof-that-lmin-is-not-in-core
Post a Comment