Ode to my students + moralizing

First, two tales of hubris and folly. The recursion theorem was a big success with my students. We don't usually teach it in this course, but my students went through the standard material like pie and were hungry for more. Other than a ridiculously easy proof of the undecidability of the halting problem, the recursion theorem yields a slick proof that L_min is not in RE (good luck approaching that one without this tool). Riding a euphoric wave of success, I thought I'd improvise a proof that L_min is not in coRE. I thought I had a clever proof using the fixed-point theorem, but it turned out to be wrong. After spending a couple of days in search of a proof, I turned to mathoverflow (an amazing resource!) where Ryan Williams produced a correct proof.

Second, during the last lecture, a student asked if every undecidable language in RE is complete for RE under mapping reductions. I thought the answer should be true, and tried to prove this during the break. Needless to say, I failed to find a proof. After speaking with Menachem Kojman, I learned that in fact the answer is false; this follows froom the Friedberg-Muchnik theorem.

There are two morals to this story:
1. I was blessed with amazing students this semster.
2. Sometimes (if one is lucky!) innocent-sounding questions that come up in undergraduate lectures turn out to be deep, difficult research problems. By all means attempt to tackle them, but keep in mind this caveat.

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.

A cheating Quine?

So I'm teaching a course on automata theory -- again. (A brief personal update: I've started a faculty position at BGU, got married and had a baby -- not in that order.)

I want to teach the recursion theorem this week. The theorem states that no matter what Turing machine one is designing, one can always assume that it has access to its own description.

To me, this always seemed painfully obvious. Once you accept that Turing machines and programs (in MATLAB, say -- to be concrete) are equivalent, the argument comes down to writing a program that can print its own code.

At first, writing a program that prints itself might seem impossible. After all, any sort of program that says PRINT X will be longer than the string X (because it contains X and the PRINT instruction) -- and so X can't be the program's whole description!

Indeed, such a simple strategy for a self-printing program is doomed to failure. However, who says the program must quote itself within itself verbatim? Maybe it can encode a description of itself in some compressed form, and execute a routine that decompresses and prints that description. Indeed, many such programs exist -- they are known as quines (after the great logician and philosopher Quine).

But it seems to me that these quines, while clever, are working too hard. Consider the following simple MATLAB function:

function quinecheat
fid = fopen('quinecheat.m','r');
str = char(fread(fid))';
% remove double line-skips:
str = strrep(str,[char(13) char(10)],char(10));
fclose(fid);
fprintf('%s\n',str);
return

If you save the code above as the MATLAB file 'quinecheat.m' and call quinecheat from the MATLAB command window, you will get a printout of the code.

On the one hand, you can do this in just about any programming language -- and any Turing machine T can assume it's being simulated on some universal Turing machine U and move U's tape head to the beginning of T's description. Also, I believe that this trivial "proof" of the recursion theorem retains the theorem's full power. For example, here is a simple proof that the halting problem is undecidable. Suppose to the contrary that some matlab function H inputs other matlab programs and outputs 1 if the input program halts (and 0 otherwise). Now consider the matlab function D which obtains its own description [D] and calls H([D]). If H([D])=1, D goes into an infinite loop; otherwise, D halts. We've reached our contradiction!

And yet I can't help but feel that I'm cheating somewhere. Is my program quinecheat a valid example of a self-printing program? Is the technique I am suggesting a valid alternative proof of the recursion theorem?