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:
fid = fopen('quinecheat.m','r');
str = char(fread(fid))';
% remove double line-skips:
str = strrep(str,[char(13) char(10)],char(10));
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?