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.
Can this Universal Machine be used as the ULTIMATE microkernel for an operating system? Imagine an implementation of Linux running on a 34 byte picokernel!
cpeterso
yup... didnt even stand a chance...
The server was probably running at a bandwidth of 34 bytes.
Remember "Bring 'em on"? *sigh
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).
;-)
Funny, i'm sure they said ``plain english translation''
0xC3
But does it run Linux?
- 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
"Turing machine"
Hah. 14bytes.
15 counting the null terminator, but that is neither here nor there!
Imagine a Beowolf Cluster of THESE!!!
Here's how to crash the machine :
Enter a combination or a definition.
Names are single characters; whitespace is ignored
An empty definition like "P=" undefines a name
Predefined names are
Y ? U S $ P K I 1 0
Example inputs are: Sxyz, U"I110", 2fx=f(fx), Z=222(P0), U"Z"
Sxyz
of size 4
head reduces in 1 steps to xz(yz) of size 4
xy=x
defines x as SSK(S(K(*))K)K of size 13
222(P0)$
of size 25
head reduces in 0 steps to 222(S(*)(KK)K)(KK) of size 25
"Z"
java.lang.RuntimeException: Variable can't toBinaryString()
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.
As soon as I saw it in the back of the latest Spider Man comic, (on the back of the page which advertises X-Ray specs, which by the way, don't really work, trust me, save your cash!) I just knew I had to have one. It took me all summer saving up the money for one mowing lawns, collecting bottle caps, and painting fences. But all that hard work paid off, during the last week of August, when I got my shiny new Universal Machine in the mail.
I remember like it was yesterday how my hands trembled, as I tore the wrapping off the box. Sweat dripped from my face and stung my eyes in the mid-afternoon heat, as they had so many dusty days of mowing and painting, but it was all worth it!
My Universal Machine does EVERYTHING! I set it in my pet hamster's cage, and it exercised Herbie (my hamster) till he was tired and sleepy. I then took it out and used it to clean the dishes and take out the trash (my chores) which it did AUTOMATICALLY!
Then, as the sun was setting, I used my Universal Machine to walk Sparky (my dog), which it did all by itself. It even cleaned up after him. I was amazed!
When school started, I used my Universal Machine to do my homework, which it did with no intervention from me! Then, my friend Bobby and me used it to make two fake ID's and disguises to get us into an R rated movie... there's nothing it can't do!
I used to love using it to scare my older sister and her stupid high-school friends, or chase the neighbor's cat up and down the street. Now, mostly I let my Universal Machine do everything for me, since it's universal, it can do anything and everything, and since it's a machine, it never gets tired or bored or complains.
In short, I wholeheartedly recommend the Universal Machine to anyone who wants a machine which is universal. It even processes S and K commands. It does absolutely EVERYTHING.
Sincerely,
Timmy B. Stevenson
Atlanta, Georgia
SKK this.
I could not justify my existence if I were a turkey farmer. Would I terminate myself? Undoubtably, yes.
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.
Old COBOL programmers never die. They just code in C.