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.
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...
That is all.
yup... didnt even stand a chance...
The server was probably running at a bandwidth of 34 bytes.
Remember "Bring 'em on"? *sigh
- 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
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.
"Turing machine"
Hah. 14bytes.
15 counting the null terminator, but that is neither here nor there!
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
I can create a one-byte universal machine. It's in a language I called "MWoodylazium." In this language, a 1 is interpreted as a universal machine. A 0 is a rabid flying monkey. OK, here's my code:
--- Begin program
1
--- End program
See, wasn't that easy? I should note, though, that this is the second version of my program. The first version is still at large in the greater Manhattan area.
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.