Trade

A computer program that trades places with all possible inputs

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. It also implies 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 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. Below, 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.- Lawrence S. Moss

 

A computer program that trades places with all possible inputs