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:Universal Machine == Universal Turing Machine?

[zook]

They're the same in that any problem written for one can be written for the other.

The idea is that a universal machine is one that any algorithm can be executed on. Of course, this depends on what you call an algorithm, but most reasonable definitions are equivalent here.

I think of a Universal Turing Machine as a specific implementation that meets this requirement. Specifically, a state machine coupled to an infinite tape. There are plenty of other viable machines: infinate register machines, c code with infinite memory, etc.

Re:Ummm.... Plain English translation?

[Uller-RM]

Hehe... the point is, what's the most minimal machine you can build that can solve a given class of problems?

Layman's example - It's the concept that you could theoretically rework the Quake3 engine to run using the 8088's capabilities. (I say theoretically because some Slashdot nitpicker is inevitably going to try to karma whore by pointing out that 8088s could only use 16 bits of memory addresses, and you'd need way more.) The point is that given the 8088's instruction set, it's theoretically possible to emulate a 32-bit protected mode, and graphics, and so on and so on until you had one frame every hour of Quake 3. Now, try a Z80. Back on down the chain... what is the most minimal machine possible that can still run a translated version of today's software?

One of the major ideas in Computer Science is what sorts of questions and problems are difficult, or absolutely downright impossible, for a given type of machine to solve. In particular we like to talk about Turing machines, which are damn minimal :) (See the parent for a rough description.) Any machine or language that can be used to solve the same class of problems as a Turing machine is said to be Turing-equivalent - most every conventional machine out there is Turing equivalent.

(There are problems that Turing machines can't solve - the classic one is the halting problem. Can you write a program that can look at any other programs (not just most programs, ANY program in the infinite universe, including itself) and say if it'll lock up or not? With a Turing-equivalent machine, it's fundamentally impossible to do that - not just improbable or hard-to-implement, but impossible. The solution is to create a machine that's more capable than a Turing-equivalent machine, but that's rather tricky with macroscopic physics.)

This is just a very rough intro - the article is that this guy came up with a CFG (Context-Free Grammar) with only two rules that apparently is capable of arbitrary computation of functions, which is damn cool. The site is slashdotted, so I've only read the top HTML page, not the Postscript paper :\