Lawrence S. Moss
-
A computer program that trades places with all possible inputs
Believe it or not, the image above really is a computer program. It is connected to this semester's Recursion Theory course.
In 1938, my academic grandfather Stephen Kleene published a paper containing a result called the Second Recursion Theorem. This result has many consequences in many areas of mathematical logic. As just one of its minor consequences, it implies the famous result that in any programming language, there is a computer program self such that running self outputs self itself. The program below, trade, has an even stronger property. To state it, we must consider programs running on other programs in the same language.
When trade is run on any program p, the output would be the same as the result of running this same program p on trade. Although the existence of trade follows from the Second Recursion Theorem, it seems that nobody exhibited a trade program in full glory. Above, you'll find a portion of such a trade program, written in a language called 1#. Programs in 1# are not readable, but the language can be explained in a paragraph that is shorter than this one. The trade program has 13,035 instructions. Some of the parts in color are independently interesting: the red part at the bottom is a universal program.
You can find out more about 1# at www.indiana.edu/~iulg/trm.
