Slashdot Mirror

← Back to Stories (view on slashdot.org)

34-byte Universal Machine

Posted by timothy on from the clever-man dept.

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 ."

4 of 258 comments (clear)

  1. Right... by sheetsda · · Score: 5, Funny

    > 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>)

  2. Hey by Anonymous Coward · · Score: 5, Funny

    Its still easier to understand than Perl code.

  3. The Null Command... by MS · · Score: 5, Funny
    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

  4. For all the braintrusts posting smaller solutions by Jerf · · Score: 5, Funny

    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.