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

Re:Ummm.... Plain English translation?

[Stonehand]

A universal Turing machine is one that is capable of simulating all other Turing machines. That is, where Turing machine M would run program P, for a UTM you can come up with a sequence M' such that UTM(M',P) = M(P).

And a Turing machine is a state machine whose only storage (beyond "what state am I?") and I/O is done with a sequential tape. So the machine can read from the tape, and then act based on its current state -- said actions including overwriting the symbol, or perhaps going forwards or backwards on the tape, plus changing state.