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

Right...

[sheetsda]

> 222(P0)$
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)) (SKK(S(*)K)))(SKK(S(K(*))(*K(*(*))))(SKK(S(*)(*(*) ))(KK)))))) of size 167
outputs 16 bits "0000000000000000"

pfffffttt... Well duh. Anybody could see that.

(</sarcasm>)

Hey

[Anonymous Coward]

Its still easier to understand than Perl code.

Re:slashdotted

[Decimal]

yup... didnt even stand a chance...

The server was probably running at a bandwidth of 34 bytes.

The Null Command...

[MS]

This reminds me of:

• 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

I can beat 34 bytes.

[crandall]

"Turing machine"

Hah. 14bytes.

15 counting the null terminator, but that is neither here nor there!

I can beat that.

[MWoody]

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.

Re:I can beat that.

[shogun]

In this language, a 1 is interpreted as a universal machine. A 0 is a rabid flying monkey.

Ok well heres my contribution:

--- Begin program
0 0 0 0 0 0 0 0 0 0 0
--- End program

Fly my pretties! Fly!

Re:34 byte microkernel operating system?

[aminorex]

Yeah, *one* would be slow, but...

Imagine a BEOWULF CLUSTER of these babies!

Ok, I take that back: Actually, you could implement
this thing with, what, maybe 1000 transistors? It's
the ultimate RISC CPU! You could put one of them
on every column in your DRAMs, right on the silicon,
so that latency to memory would be nigh zero.
The resulting machine would be just like a CM-1, with
no router. Add a router, and *bang* you've got
the ultimate fine-grained MPP.

ARGHGHH!

[Skim123]

Here I am, taking a break from studying for my Programming Languages final, so I meander on over to /. and see: LAMBDA CALCULUS and COMBINATORS, the same stuff I've been studying for the last few hours. Sigh.

SKK this.

For all the braintrusts posting smaller solutions

[Jerf]

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.

S-K++

[supersnail]

Language enchanced with the addition of the "U" and "C" instructions.