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 ."
I don't have time to look at the article at the moment, but the headline reminds me of BrainFuck. It's a cute little language that emulates the functions of a Turing machine.
Maybe someone can brush me up on my theory: is a Universal Machine a Turing Machine?
A universal Turing machine is essentially a computer as we know them. It is a Turing machine that is capable of emulating the behavior of any other Turing machine. Since no one has yet disproved the Church-Turing thesis, this means it is a computer that is as powerful as any model of computation yet devised.
The link seems to be slashdotted, so I can't see whether he has come up with a way to make a UTM using fewer states than previous ones, or just a way to encode one in fewer bits.
I think I heard somewhere that there is a correlation between the optimal number of states in a UTM and the number of states a human can actually keep track of unaided by a machine. That's food for thought as to whether humans can do anything that is "extra-computational." That is, whether we are more powerful than Turing machines.
http://www.google.com/search?q=cache:LWZtImLLCpoC: www.cwi.nl/~tromp/cl/cl.html+John%27s+Combinatory+ Logic+Playground&hl=en&ie=ISO-8859-1
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.
--
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
The trouble with the one-combinator model is that it's not a supercombinator. The reduction rule of X introduces lambdas, which is of no practical use, since the whole point of using combinators to begin with is to remove the lambdas.
As far as I know, it has not (yet) been proven that you need at least two supercombinators to implement all of lambda calculus, nor has it been proven that you can do it with only one.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
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.
I use SK as the back end of my functional programming language. I added two more: Sl and Sr
Sl a b c => (a c) b
Sr a b c => a (b c)
(I think Turner calls these B and C, corrections pls)
It's pretty easy to see that S/Sl/Sr are the optimal 1-ary combinator set. You hardly need K, and you don't need to generate I during compiles (but it's handy during eval to preserve sharing).
John