34-byte Universal Machine

N. Megill writes: "Computer scientist and obfuscated code aficionado John Tromp has devised what may be the world's most compact Universal Machine (Postscript research paper) to date. Written in the 'S-K combinatory logic' language, which has only 2 commands (S and K), his UM can be encoded with only 272 bits (34 bytes), compared to 5495 bits for the Universal Turing Machine given in Roger Penrose's book The Emperor's New Mind ."

Comments

Nice result

[frank_adrian314159]

This is a really nice result. The only thing I would wonder about is whether you can get your Y-combinator in less than 12 S/K's. Since equivalent forms all left-reduce to the same string, you should be able to build and enumerate tree's easily enough, so I wonder why they didn't do this to claim an official "absolute result" for the smallest Y-combinator...

Re:I can beat that.

[quintessent]

I'm afraid Mr. Woody's point is correct. He was showing that the shortness of a "Universal Machine" program will depend on the language you use. If your language's compiler compiles a binary 1 into a universal machine, then it's pretty easy to code one up. I could code Linux into one bit if I wanted to. The compiler would be kinda big, though.

This also has interesting implications for DeCSS. Is the bit 1 a circumvention device? Then 0 must be too, since we can just invert the rule.