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