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>)
It's a model of computation, based on the S and K combinators (as used in functional programming). It's similar in concept to the Turing machine, in that it's a basis for computation, and a model to base implementations on. The Turing machine models an imperative computational style, while combinatory logic models a style more akin to the lambda calculus.
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!
If you are feeling masochistic, you can try David Madore's Unlambda programming language. It is built around (in its basic form) the S and K combinators. Of course for all the Schemers out there, David is nice enough to include a form of call/cc for maximum obscurity. This is by far my most favorite of the painful programming languages.
--
It was (as I recall) built out of around 100 TTL chips on two cards all using verowire technology (yuk). My responsibility was to write the microcode that directly executed the various combinators. We ended up supporting around 20 operators, starting out with S, K, I, and then progressing through B, Y, and some simple numeric and comparison operators. The garbage collector was written in one (long) night as the result of a bet!
It worked remarkably well considering the date (1979-1980). Unfortunately, I couldn't find a copy of the paper that describes it online anywhere.
One of the cool things about SKIM was that you could enter infinite programs, and since they were evaluated lazily, things just worked. For example, you could define a function that returned the infinite list of prime numbers. Actually what it returned was a code fragment that evaluated the list, and as the caller needed those values, the list would be evaluated, and the code fragement pushed backwards down the list.
We never thought of building a UTM - now it has been done, it seem obvious!
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.
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.
-I like my women like I like my tea: green-
Combinator calculus actually has a *practical* application. No kidding. In fact, the whole beauty of combinators is that you can reduce lambda-expressions into a variable-free, but equivalent form (via the `bracket-abstraction' algorithm).
Anyway, the point is, if you're writing the back end for a functional language... wouldn't it be real swell if you all had to implement was two combinators? No dealing with messy variables either. This is exactly the approach taken in the implementation of the functional language Miranda. (Although for reasons of efficiency, there are more than 2 combinators... you *could* use just S and K, but then you get some REALLY HUGE results for even relatively simple lambda-expressions).
So combinatory logic isn't just the domain of Schoenfinkle, Haskell Curry and assorted logic fetishists... it can and has been used for `real life' applications too.
for those familiar with SKI combinatorial expressions and Lambda terms it is always a fun thing to see that I can be expressed in S and K by:
Ix = SKzx = Kx(zx) = x
But did you know that you can reduce the language to one-combinator?!
X = lambda f.fS(lambda xyz.x)
K => XX
S => X(XX)
The proof to this particular variation of a one-combinator basis for Lambda-terms was first published by Fokker, University of Utrecht The Netherlands, and shows that among several variations of one-combinator basis Lambda terms his is the shortest.
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.
I can crash it by scrolling down to read the page, and then scrolling back up to play with the applet. It doesn't repaint correctly and I have to hit reload. This is with Sun's Java plugin, version 1.4, on IE 5.5. Incredible. It's been 6 years and they still can't make applets work.
Old COBOL programmers never die. They just code in C.