Slashdot Mirror
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 ."
> 222(P0)$) (SKK(S(*)K)))(SKK(S(K(*))(*K(*(*))))(SKK(S(*)(*(*) ))(KK)))))) of size 167
of size 46
head reduces in 53 steps to S(S(K(S(SKK)))KK)(K(SKK(S(K(S(*K)))K)(SKK(S(K(*K)
outputs 16 bits "0000000000000000"
pfffffttt... Well duh. Anybody could see that.
(</sarcasm>)
Its still easier to understand than Perl code.
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.
Only the dead have seen the end of war.
- Every program has at least one bug
- and can be shortened by one instruction
which induces that the "optimised" program will have no instructions, and obviously won't work.ms
Hehe... the point is, what's the most minimal machine you can build that can solve a given class of problems?
:) (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.
:\
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
(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
For all the braintrusts posting solutions they claim are smaller then 34-bytes, and are in grave danger of spontaneously being awarded the Nobel Prize in Mathematics by the suddenly humbled mathematics community, remember the encoding your specify your Universal Turing Machine must be the same encoding as the Turing Machines you will be running the UTM on.
The posted "single bit" solution doesn't work. The only machine encodable in that language is the claimed UTM... but that means that the UTM is far from a UTM, and is in fact a Nothing-TM. Don't hold your breath waiting for your Nobel.
The others have similar problems. The string "Turing Machine" isn't a specified encoding.
Joke all you want, I guess, but pay more attention in theory class, please.