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!
I don't think this guy came up with S-K Combinatory Logic. I think that's old. But he, apparently, was the first one mad enough to use it to define a Turing Machine. :)
:)
So what's so great about that? Um... well, I guess it's just the academic world's version of "Hey! Look! I can code a scrolling text demo on the 6810 processor using only 33 bytes and 272 clock cycles!"
I.e., no practical applications, just a "cool thing".
It all dates back to the 1930's (when a lot of great math was done). Alonzo Church tried to define what a "computation" was, and came up with something called "lambda calculus". Alan Turing, independently, did the same thing, and came up with the "Turing machine". It was eventually proven that these two definitions are equivalent: anything you can compute with lambda calculus, you can compute with Turing machines, and vice versa.
Actually, ALL computers are equivalent to Turing Machines. No matter how advanced a computer is, every computation it can do, can also be done on a Turing machine, only slower.
I think some other guy invented combinatory logic (was it Curry?) as an alternative to Lambda Calculus. It, too, can perform any computation possible. It's just simpler, S-K combinatory logic being the simplest, with only two operands/operators. So the definition is very simple, it's just damn hard to read.
So mathematicians proved long ago that these different ways of defining computations are all equivalent. Mathematicians usually only care about proving that things CAN be done. Once they've proven that, they don't care about actually doing it. So defining a Turing machine using combinatory logic is just a "cool thing", it doesn't have any theoretical importance.
But I haven't read the article, so maybe the guy did something else with it that had importance.
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.