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

Comments

Real computer scientists don't write code.

[Starship Trooper]

They occasionally tinker with `programming systems', but those are so high level that they hardly count (and rarely count accurately; precision is for applications.)

Ummm.... Plain English translation?

[strredwolf]

What does this all mean? What kind of virtual machine is this? I can't tell...

Re:Ummm.... Plain English translation?

[Mr Windows]

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.

Re:Ummm.... Plain English translation?

[Stonehand]

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.

Re:Ummm.... Plain English translation?

[dannywyatt]

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.

Re:Ummm.... Plain English translation?

[Ironfist_ironmined]

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

Funny, i'm sure they said ``plain english translation'' ;-)

Re:Ummm.... Plain English translation?

[Anonymous Coward]

But does it run Linux?

Re:Ummm.... Plain English translation?

[Hater's Leaving, The]

It's effectively a set of rules for substitutions. That's about as broad brush as I can make it, in order to try to get it to appear similar to
- Church's lambda calculus
- Post's strings
- LISP
There is no real 'machine' that's being virtualised. It's wholy abstract.

Phil

Re:Ummm.... Plain English translation?

[RandomInAction]

Power is an interesting term, a Sinclair zx can carry out any task, that any computer so far created can carry out. It just takes longer. As a 'pure' model you are correct. But there are other aspects/interpretations of power.

Re:Ummm.... Plain English translation?

[PD]

Not necessarily. Turing machines do not exist in real life, because they are necessarily infinite machines. A Sinclair has just a measly amount of memory. A Turing machine could compute anything a Sinclair could, but not the other way around.

Re:Ummm.... Plain English translation?

[RandomInAction]

Sinclair zx can carry out any task, that any computer so far created can carry out. It just takes longer Yet this is still true, is it not?

Re:Ummm.... Plain English translation?

[Uller-RM]

Hehe... the point is, what's the most minimal machine you can build that can solve a given class of problems?

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 :) (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.

(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 :\

Re:Ummm.... Plain English translation?

[PD]

No, because the problem statement could be larger than the computer. For example, I might have a billion random numbers to add up. The sinclair could not hold the beginning data set, nor could it compute the dataset from a smaller function.

Re:Ummm.... Plain English translation?

[ToLu the Happy Furby]

One nitpick:

When you say,

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

it seems as if you're implying that a quantum computer would be more than Turing complete, and/or might be able to solve the Halting problem. This is wrong. It *may* be the case (AFAIK this hasn't been proven yet) that a quantum computer of arbitrary size could be used to solve all problems in NP in polynomial time/space in the length of the inputs (at least, if you don't believe the many-worlds interpretation of quantum theory) even if NP != P. In other words, a quantum computer of arbitrary size may be able to serve as the oracle that you need for the naive way to solve any problem in NP in polynomial time, even if a Turing machine could never solve NP-Complete problems in poly time in the length of the inputs.

This is *not* the same as being able to solve an incomputable problem--i.e. those which a Turing machine may take infinite time to solve (the original example being the Halting problem)--even though it would represent the first greater-than-polynomial improvement on the Turing machine yet. (Assuming that a quantum computer is, in fact, equivalent to a nondeterministic Turing machine.)

Re:Ummm.... Plain English translation?

[Pussy Is Money]

Would just like to add that the halting problem is mostly useful as a theoretical device for very generally proving or disproving propositions about specific machines, rather than as a practical problem that needs a solution though. In reality simple watchdog timers perform almost as well as a human would in assessing whether a particular program will ever end or not (also programmers tend to just avoid endless loops in their programs).

Re:Ummm.... Plain English translation?

[ashre]

This universal machine uses Combinators, specifically S-K combinators.

S-K combinators (and other combinations) like Turing Machines and Lambda calculus can express everything we can possibly compute (all possible computations).

Expressions are built up by applying combinators (eg A and B are expressions AB is an expression with A applied to argument B).

Primitive combinators define reduction rules. In S-K combinators we have the primitives S and K.

K is defined as: (K x) y -> x
for any expression x and y.

S is defined as ((S f) g) x -> (f x)(g x)
for any expression f, g and x.
(x, y, f and g are just part of the notation not variables)

By applying S and K you can build up expressions expressing all possible computations (though not very compactly).

You can now repeatedly apply the two rules to an expression to obtain a normal form (or repeatedly apply to the left most reducible element to obtain a head normal form).

For example:

S[1]K[1]K[2]S[2] -> K[1]S[2](K[2]S[2]) -> S[2]

(the square brackets indicate subscripts for the purpose of telling the combinators apart - they imply nothing)

And S[2] is a normal form.

Many other combinators are normally introduced to increase expressiveness but above you have the basic principles.

Marc

Re:Ummm.... Plain English translation?

[metacell]

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.

Re:Ummm.... Plain English translation?

[r00tarded]

a multiprocessor (multituring) can solve the halting problem. its not cheating is it....?

Re:Ummm.... Plain English translation?

[ncc74656]

a multiprocessor (multituring) can solve the halting problem.

How? The machine returns its answer when it stops—it returns one value if the program ends normally or another value if it crashes. If you feed it a program that runs forever (doesn't crash, doesn't end), it'll never be able to determine a correct answer. How does using multiple machines change this?

Re:Ummm.... Plain English translation?

[Uller-RM]

Haskell Curry invented a variation on lambda calculus now called Curried functions. They're used in the increasingly popular functional language (guess it's name...) Haskell.

Re:Ummm.... Plain English translation?

[Uller-RM]

I suspect that a QC isn't capable of solving the halting problem in general - however, it would be far easier to evaluate finite instances of the problem than with a conventional machine.

I haven't given it much thought at this juncture, but it seems to me that one could reduce a Turing machine program to a unitary matrix, and then supply the Hadamard operator as input (i.e. a superposition of all possible inputs, equally likely) - thus evaluating the program on all possible inputs at once. Based on this line, if the resulting quantum state wasn't representable as a tensor product of basi, the program would halt.

The above probably wouldn't work, but at least I'm thinking it over :)

Re:Ummm.... Plain English translation?

[Fjord]

It's pretty important to know that a computer without a hardware random number generator is a "von Neumann machine" which is a Turing Machine with limited memory (so not as powerful as a Turing Machine, which has an infinite tape). Thus, a UTM can solve any problem a von Neuman machine can, and thus is a fully functioning computer. Obviously, in practise, this UTM can only be run as a von Neumann.

Re:Ummm.... Plain English translation?

[dannywyatt]

If the data is larger than the computer, then the computer is not equivalent to a Turing machine.

But you could multiply large primes with a Sinclair, you'd just have to be willing to spend a long time feeding it cassette tapes...

Re:Ummm.... Plain English translation?

[RandomInAction]

A Sinclair, or other computer is not defined by the data set, a Sinclair or even any current super computer could deal with any finite data set. The same thing is true for and Turing machine. What is this 'beginning data set' you talk of? I guess you'd expect a p4 to manage it? Well a p4 could also handle a billion, billion, billion, billion elements, or more it's just another Turing machine like the Sinclair. It'd just take a long time. I believe that you have utterly misunderstood the UTM.

Re:Ummm.... Plain English translation?

[David Price]

You're right, of course - throwing more processors at the problem does not evade Turing's uncomputable brick wall.

There's an interesting example that one of my professors pointed out in class - a kind of problem for which being multithreaded (not necessarily multiprocessor, just an environment in which you can spawn threads, are guaranteed bounded waiting for your next turn at the processor, and can kill off threads) actually buys you the ability to solve more problems.

Consider the problem of reducing Boolean expressions to their truth values. Now add a twist: in addition to the values T and F, you introduce a value B (bottom). Trying to compute the truth value of B results in an infinite loop, so, for instance, a program that tries to compute the truth value of the expression "T AND B" never returns a result. This is the correct behavior for such a program; neither true nor false is the right answer, so the program goes into an infinite loop.

The interesting thing is when you consider boolean short-circuiting. What's the value of "F AND B"? If you're using a short-circuiting AND operator, you see the F, decide not to bother with the right hand side, and return F as the value of the expression.

But now order matters: "F AND B" returns F, but "B AND F" never returns. This doesn't seem to make sense; in both cases you'd like to return F. Boolean operators should be commutative, even in this new world where you might randomly blow up upon encountering the value B.

The solution is to implement your AND reducer as a function that spawns two threads which are handed each side of the expression. It returns T if both threads return T; if either thread returns F, the other thread is killed off and F is returned. A similar trick is performed for the OR reducer.

The result is that you can now compute the truth values for all expressions that have Bs only in parts of the expression which are not necessary to compute due to short-circuiting. A straightforward, single-threaded approach will go into infinite loops for some inputs that this method will find a result for.

Re:Ummm.... Plain English translation?

[_Knots]

Incorrect.

Formally, a n-CPU system is really equivelant just a Turing Machine with n times more internal information (data memory, data cache, disk data, etc. may all be considered "internal state", with the program residing on the tape still). Thus, if one UTM couldn't ever solve the halting problem, N of them in parallel could never solve it either.

Now, I can't speak towards a NDUTM, or an array of NDUTMs or QC. Would be nice (though unlikely) if every problem we can ask had a P-time solution (string theory computation?) - but the truth probably is that there's P, NP, NP-complete, and generally unsolvable problems (halting). But computation theory is still new, so maybe what I consider "probable" isn't.

_knots

Re:Ummm.... Plain English translation?

[Pr0xY]

you can simulate math from a higher bit machine on a lower bit machien so it is entirely possible. I have many times performed a 16-bit multiply and 16-bit additions on a 6502 (which is an 8-bit machine with VERY limited abilities).

It is of course doable, but it would be significantly larger code, and of course slow to the point of unplayability...but you cant win em all ;)

Re:Ummm.... Plain English translation?

[kwan3217]

In theory it could... translate Bochs (An x86 system emulator) into its language and then run linux on that.

Re:Ummm.... Plain English translation?

[Preposterous Coward]

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.

Well, since you brought it up...

The 8088 could actually address 20 bits of memory (1MB), a relatively impressive feat at the time, though you had to use that goofy addressing technique with segment:offset registers and 64K pages. Of course, if 1MB was not enough you could always swap stuff out to slower storage (e.g. disk) -- a technique that I became altogether too familiar with in the Z80 days when machines had 64K of *total* RAM that was expected to accommodate your OS, code, and data all at once.

Anyway, I am just nitpicking because it's the Slashdot way. I think your explanation was actually quite informative. (And I'm not whoring for karma either -- hit the max a long time ago.)

Re:Ummm.... Plain English translation?

[millette]

You mean it's just like Microsoft's CLR? Why did Turing copy Microsoft if Microsoft is so crappy?

Re:Ummm.... Plain English translation?

[darweidu]

However, a single processor machine could be multithreaded, giving equal time to each short-circuit evaluation and therefore still solve the same problems the MP machine could.

Re:Ummm.... Plain English translation?

[Isle]

The problem with the "halting problem" is there for turing machines in case there exists are halting function can be written functions that are self-contradictions. Example:

if I dont return => return
if I return => goto infinite loop

Thus the halting function with a boolean return-value, is not just impossible to compute, it also has an incomplete definition.
The solution is ofcouse to extend it and allow additional return values. One extention could be to have an extra "I have self-contradiction" value, but that leads to new problems.

More interesting for quantum computers is the possibility for bools to have the value true AND false, and neither true nor false.
That would solve the above problem, but would like the Schrödinger cat, be a little too wierd for most people to swallow.

Re:Ummm.... Plain English translation?

[lhdentra]

No matter how advanced a computer is, every computation it can do, can also be done on a Turing machine, only slower.

Unless it's a fast Turing machine.

Re:Ummm.... Plain English translation?

[PD]

A Turing machine is a machine that uses a tape, a read/write head, and a set of rules to solve an equation.

The equation that I wish to solve has a trillion arguments:

f(x1, x2, x3, ... x1000000000000)

The turing machine sets up the arguments on the tape.

It is quite clear that a Sinclair is not a Turing machine. Turing machines are infinite, Sinclairs are finite.

Re:Ummm.... Plain English translation?

[Torville]

Okay, why won't this work...

The Turing machine stores the state of the emulated program at every step. If the emulated program currently has the state that it had at any point in the past, it's in a loop and will continue forever. If not, there are only so many states... a LOT, mind you, but finite... and it will eventually terminate.

Re:Ummm.... Plain English translation?

[mvw]

The Turing machine stores the state of the emulated program at every step. If the emulated program currently has the state that it had at any point in the past, it's in a loop and will continue forever. If not, there are only so many states... a LOT, mind you, but finite... and it will eventually terminate.

The Turing machine is not just a state machine. One thing you neglect is the dependency on input data.

A Turing machine is an abstract cpu together with a program which reads a finite number of strings as input and has a string as return value:
String f(String s1, String s2, .., String s_k)
What you describe might or might not decide if f("hi") halts, but certainly not f(s) (s some arbitrary String) in general, where you have to do your simulation for every possible s, from which there are infinitely many differents ones.

Re:Ummm.... Plain English translation?

[Isle]

The turing machine has an infinite number of states. But you are right in limited state machine(n) it IS possible to solve the halting problem. It just cant be done with machine itself,
it only requires another machine with the factorial(n!) number of states ;-)

Re:Ummm.... Plain English translation?

[cduffy]

You're trolling, right?

Turing lived and died long before Microsoft was founded (or the digital computer was created).

The image of the code is a nice touch...

[IIOIOOIOO]

Kind of give's a different spin to Steganography.

Right...

[sheetsda]

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

Re:S-K combinatory logic?!?

[tenman]

Not binary at all. While it has only to instructions, you can still deal with i/o in a broader range than 0's & 1's

Re:52.8KB widening

[ed 'g3']

Thanx for that meaningful contribution to the topic at hand.

That's what leadership is about

[oever]

So this means everything can be said in 34 bytes!
This proves it: emperors and other leaders prefer using short commands.

Re:That's what leadership is about

[stilwebm]

Castro just likes some redundancy in his messages...

Ive been doing the same thing for years.....

[CDWert]

"obfuscated code aficionado" hell my code, most of it , just like my slashdot posts is so obfuscated a month later I cant even understand it.

From the article....

I=SKK
Y=SSK(S(K(SS(S(SSK))))K)
Pxyz=zxy
0xy=x
1xy=y
?xy=1
$x=0

Maybe Im a bit tiered but dosent this sound a little Orwellian to all you ? "2+2=5"

Hey

[Anonymous Coward]

Its still easier to understand than Perl code.

Re:Hey

[dynamicexpression]

lmao :o)

Re:Hey

[PhoenxHwk]

And easier to maintain than Lisp! :)

Universal Machine == Universal Turing Machine?

[LordSah]

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?

Re:Universal Machine == Universal Turing Machine?

[zook]

They're the same in that any problem written for one can be written for the other.

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.

Re:Universal Machine == Universal Turing Machine?

[quintessent]

So a Universal machine would be anything that implements a language that is Turing complete, of which a Turing machine is an example, no?

Re:Universal Machine == Universal Turing Machine?

[zook]

The short answer is yes, although there's a bit of an overloading of the term "language" here.

The point is that a Universal Turing Machine is a Turing Machine that accepts any other Turing Machines as input, and then executes it. This is interesting, but seems kind of mundane these days since we're used to it.

To cast this into something more concrete, consider C programs (with infinite memory, blah, blah). In this language, a C-Machine is any program that I've written, whereas as Universal C-Machine is a particular program which takes as input a C program and executes it.

My OS + compiler is an example of this. I give it any program, and it is compiled and run. This is where the univerality comes in.

There is something to be shown that I can have one system like this that can describe itself. These days it seems hard to conceive of it being otherwise, however. The fact that the machine could concievably run itself is where things really get interesting.

Not all languages are able to do this. I can't do the same thing with regular expressions, for example.

My point in the original reply was that this not be done with Turing Machines specifically, but any such structure is fine. C is one example.

I've just realized that I've answered more than you asked, but now the easiest thing to is hit submit and let you sort it out. :)

34 byte microkernel operating system?

[cpeterso]

Can this Universal Machine be used as the ULTIMATE microkernel for an operating system? Imagine an implementation of Linux running on a 34 byte picokernel!

Re:34 byte microkernel operating system?

[protonman]

Sure. It would only be really, really, really slow. You know, just how zipping all your .doc documents makes using them slower; you have to unzip 'em first -> takes time.

Re:34 byte microkernel operating system?

[aminorex]

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.

Re:34 byte microkernel operating system?

[Ivan the Terrible]

If I remember correctly, the OS [sic] for the processor on the Smart Dust project was about 150 bytes. It really only implements co-routines, but co-routines form the basis for multitasking in Windows 3.1 and Mac OS less-than-X.

Re:34 byte microkernel operating system?

[cpeterso]

oh, cool. thanks for the link! I had read about a "smart dust" project at Xerox PARC that was using Aspect Oriented Programming, but it was mostly vapour at the time..

Re:34 byte microkernel operating system?

[cpeterso]

For those who are interested, the actual link to the Smart Dust software project is Tiny OS: An operating system for Networked Sensors.

Re:slashdotted

[Victa]

Kind of like a call to "Brace for impact", or "Batten down the Hatches"?

Sounds like a good idea to me...

ObYouKnowWhat

[kindbud]

Imagine a Beowulf cluster of these things displaying a Natalie Portman montage.

Nice result

[frank_adrian314159]

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

Re:Nice result

[Puk]

Your sig is especially appropriate right now. Do we now have a 34-byte Universal Turing Machine based in a 2-symbol language which wone one day be illegal because it has no Digital Rights Management? Is that Alan Turing I hear turning over in his grave? :P

In the words of a good friend, "It's all just ones and zeros."

-Puk, half-joking

Re:Nice result

[foobar104]

In the words of a good friend, "It's all just ones and zeros."

And in the words of somebody undoubtedly very wise, "I ain't payin' that kind of money for a bunch o' ones and zeros, no matter how much time y'all spent puttin' 'em in just the right order."

Re:Nice result

[sconeu]

In the words of a good friend, "It's all just ones and zeros."

Well, then we're all in trouble.

Re:Nice result

[LatJoor]

Perhaps digital right can be added in the standard library?

Google Cache

[segfaultdot]

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

Re:slashdotted

[Decimal]

yup... didnt even stand a chance...

The server was probably running at a bandwidth of 34 bytes.

Re:Wrong department

[kvigor]

Just because one is a dropout doesn't necessarily make one ignorant: even though you are clearly both, they are in fact independant states.

Google Cached copy

[papasui]

http://www.google.com/search?q=cache:LWZtImLLCpoC: www.cwi.nl/~tromp/cl/cl.html+&hl=en&ie=ISO-8859-1

Re:youre a fool.

[protonman]

> in binary

Now who's the fool? An *essential* part of TMs is that the alphabet they can use is limitless!

Give the man a break!

Mirror: Download the PDF version of the PS

[jager22]

I just decided to make a PDF of the PS file. You can download it here.

Re:Mirror: Download the PDF version of the PS

[SamBeckett]

omg u must have used ps2pdf or some crap, that is really shitty.

Re:Mirror: Download the PDF version of the PS

[jager22]

Nope...it's just Adobe Distiller. But you're right, it is really shitty.

Re:Mirror: Download the PDF version of the PS

[SirRichardPumpaloaf]

You can thank Knuth and his crappy bitmapped CMR fonts for that. Why oh why won't people use pdftex or configure dvips properly?

The Null Command...

[MS]

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

Re:The Null Command...

[BlueMonk]

I can verify this to be true. I once tried removing the last bug from a program and squeezing out the last instruction (with some divine assistance) and boom, the program did thereupon rise into code heaven where it shall spend the rest of eternity in infinite bliss, never again to be categorized under the mere term of "program". :-)

Re:Wrong department

[Hagmonk]

The amount of ease with which slashdot users can be sucked into a flame never ceases to astound me. I think it's compulsive reply post syndrome.

I can beat 34 bytes.

[crandall]

"Turing machine"

Hah. 14bytes.

15 counting the null terminator, but that is neither here nor there!

Re:I can beat 34 bytes.

[Tom7]

Oh, what a sadly C-centric and mathematically unsophisticated world you live in!
The point is to actually *implement* the turing machine (or combinatory logic reducer) in the language, not to simply spell the english words.

Re:I can beat 34 bytes.

[doubtless]

Hey hey, if it's universal you'll have to put it in Unicode, that makes it 28 bytes, or 30 including null. hee-hee.. still beats 34 I guess.

hah

Re:I can beat 34 bytes.

[White Shadow]

"Universal Turing Machine"

Heheheh, you forgot the word "universal", so it's 24 or 25 bytes depending on whether or not you are counting the null terminator (since a universal turing machine is a specific type of turing machine).

Cached postscript/pdf/image versions of paper

[Silmaril]

A cached copy of the research paper is available in in several formats from citeseer.

Now...

[Tim12s]

Code it up in the game of life, encode linux for it, ... the possibilities are.... uh... slow.

You can try this out on your own

[aleksey]

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.

Re:You can try this out on your own

[redhog]

The nice thingg about kombinator calculus is that there's no variable names. You only have one , unnamed, argument to each kombinator. This makes the definition of the evaluator much simpler than that of the evaluator of lambda calculus (which is what Scheme/LISP basicly boils down to)...

Hehe, call/cc (call-with-current-continuation, for those that likes long names, or doesn't know what it is; it's like setjump/longjmp in C, but a continuation can be "jumped to" several times, from anywhere, even after the function in which it was created (setjump in C) has returned (once or several times)) is a really nice feature, with which you can implement both exceptions and threading...

Perheaps I should take a look at that unlambda language, I read about it somtime ago, but I don't really have time for an intensive night of hacking/reading atm...

Re:Crash the VM.....

[Zurk]

Here's how to crash the machine :

Enter a combination or a definition.
Names are single characters; whitespace is ignored
An empty definition like "P=" undefines a name
Predefined names are
Y ? U S $ P K I 1 0
Example inputs are: Sxyz, U"I110", 2fx=f(fx), Z=222(P0), U"Z"
Sxyz
of size 4
head reduces in 1 steps to xz(yz) of size 4
xy=x
defines x as SSK(S(K(*))K)K of size 13
222(P0)$
of size 25
head reduces in 0 steps to 222(S(*)(KK)K)(KK) of size 25
"Z"
java.lang.RuntimeException: Variable can't toBinaryString()

SK reducing hardware

[Old time hacker]

Back in my youth, we built an SK reducing machine -- called SKIM -- S, K, I Machine (where I = SKK).
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!

Re:SK reducing hardware

[aminorex]

Hey, got any online docs on the SKIM
arch/design/impl? I'm really getting hot about
the idea of hanging one of these off of each column
of a DRAM. Mail me at alk at pobox dot com, if
you wish.

Re:SK reducing hardware

[markov_chain]

It sounds like that would have been equivalent to emulating a microprocessor. :)

Re:SK reducing hardware

[Pseudonym]

I don't know about the physical structure, but have a read of Simon Peyton-Jones' book The Implementation of Functional Programming Languages. There will be some references in the chapter on S-K combinators.

Re:SK reducing hardware

[bigsteve@dstc]

The later SKIM work at Cambridge University Computer Lab was done by William Stoye and supervised by Arthur Norman. Some technical reports are apparently still available from the Laboratory. Look for reports written by W. Stoye.

Bill\'s PhD was on an operating system for the SKIM-2 (I think) machine. IIRC, he even ported his clone of WordStar to SKIM. The port was called FrogStar because it was reputed to be the most totally evil editor in the entire universe :-).

-- Steve

Re:SK reducing hardware

[Salsaman]

OK, then, perhaps you can explain to me what S and K actually do...are they similar to the familiar functions of computing like AND, OR, NOT, ADD etc ?

Re:SK reducing hardware

[Old time hacker]

K is the constant combinator. It takes two arguments, and returns the first one. This can be written as:

Kxy -> x

S is the spread combinator. It takes three arguments and does some spreading.

Sxyz -> xz(yz)

Try and evaluate SKK There are insufficient arguments to do anything, so lets add 'x'

SKKx -> Kx(Kx) (by the S rule)
-> x (by the K rule)

Thus we say SKK = I (the Identity combinator).

All other combinators can be built up from these two, including Y -- which is defined as

Yf -> f(Yf)

This is the magic 'recursion' operator.

I can beat that.

[MWoody]

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.

Re:I can beat that.

[Polo]

Seen on a bumper sticker the other day:
"Don't make me call out the flying monkeys"

Re:I can beat that.

[shogun]

In this language, a 1 is interpreted as a universal machine. A 0 is a rabid flying monkey.

Ok well heres my contribution:

--- Begin program
0 0 0 0 0 0 0 0 0 0 0
--- End program

Fly my pretties! Fly!

Re:I can beat that.

[cpeterso]

--- Begin program
1
--- End program


but can you prove that your program terminates?

Re:I can beat that.

[susano_otter]

That's what the rabid flying monkeys are for. Duh.

Re:I can beat that.

[WolfWithoutAClause]

> I can create a one-byte universal machine.

Hey, I can beat that. I'll name that language in 1 BIT. ;-)

It's in a language I call "WolfWithoutAClausium." 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

Re:I can beat that.

[istartedi]

I can see at least sqrt(-1) problems with that.

Re:I can beat that.

[Jerf]

Wow, nice language!

I admit I'm a little dim, though. Could you show me, say, the traditional palindrome detector in your language?

(Note to moderators: This is sarcasm. Note to MWoody: Pay more attention in your theory class. If you've even taken any.)

Re:I can beat that.

[MWoody]

Of course it has palindrome detection. I didn't say they were STUPID rabid flying monkeys, did I?

And I switched majors from CSC to English the quarter before I was supposed to take Theory of Computing. Maybe it was for the best. ^_^

Re:I can beat that.

[MWoody]

Ahhhh! You took the byte out of my rabid flying monkeys!

The other seven bits, incidentally, were my secret backdoor for any programs written in "MWoodylazium." I mean... Uh... Look! Monkey!

Re:I can beat that.

[quintessent]

I'm afraid Mr. Woody's point is correct. He was showing that the shortness of a "Universal Machine" program will depend on the language you use. If your language's compiler compiles a binary 1 into a universal machine, then it's pretty easy to code one up. I could code Linux into one bit if I wanted to. The compiler would be kinda big, though.

This also has interesting implications for DeCSS. Is the bit 1 a circumvention device? Then 0 must be too, since we can just invert the rule.

Re:I can beat that.

[Jerf]

He was showing that the shortness of a "Universal Machine" program will depend on the language you use.

No, he's incorrect. The encoded UTM much accept other Turing Machines in the same encoding. Since the specified language has only one string, which is the claimed UTM, it can accept precisely zero other TMs as input to run them; it's absolutely incapable because they can't even be expressed in that language.

Therefore, it's not a UTM. It's a Nothing-TM. It can't do anything; it's too constrained by the language.

Even if you extend the language, you'll find it does odd (and provably odd) things to the rest of the language, rendering it impossible to work with with traditional techniques. (Is that 1 a "1", or is it the UTM? Who can tell? In a proof, you need to know.)

Come on, think about it for a moment. If it were that easy, why would this news article even exist? The guy who put together the 34-number version isn't stupid; if it were this easy to get down to 1, why would he have bothered?

Combinators and lambdas and stuff..?

[mcc]

A while ago i came across this programming language called Unlambda, which is a superset of the s-k combinatorial logic calculus thing that this turing machine is written in. (not a very big superset, mind you. they added call/cc, some input/output functions, and an operator that lets you fiddle with evaluation order.. just look at the webpage i linked. it's interesting..). Thus far, about the most complicated program written in unlambda (not counting the quines) is something that prints out the prime numbers one by one as a series of increasingly longer rows of asterisks.

Now, though, it would appear that we can run a universal turing machine in unlambda! I think! I haven't read the paper closely enough yet to work out how exactly the block of encoded binary at the end functions :)

In the meanwhile, though, i'm posting for this reason: i'm really, really wierdly interested by lambda calculus and combinatorial functions and church numerals and all these other bizarre functional-programming offshoots. I can't, however, seem to find any really good resources explaining how they work. I mean, you look around on google or whatever, and occationally you'll find something explaining the basics of what an anonymous function is, and maybe explaining how to construct a church numeral or putting the old ((lambda (x x) (x x) (lambda (x x) (x x))) infinite loop thing up. But i've yet to find something that actually, you know, goes on and explains to you how to use all of this. None of them reach the point of beginning to explain how you go from knowing what a church numeral and "successor to 1" means to expressing foreach (1..10) {} using only anonymous functions.

The site with the universal turing machine links to what claims to be an overview of how to use combinatorial functions, which makes me really happy. However, i was wondering: does anyone have any good links, examples of books, etc, that explain how to construct programs using lambdas and/or combinatorial s/k functions and all that? I hear some college courses cover this stuff (although near as i can gather, unfortunately, no courses at my current college do), so there has to be some kind of information online somewhere. I'll probably find something on my own eventually, but just as long as i have your attention: is there any reading material anyone *recommends* for someone who just finds lambda calculus and such interesting?

For now, though, i'm going to read this intro to combinators thing linked from Tromp's site. Maybe it'll teach me enough i'll be able to finally realize my crack-addled dream of porting the lambda calculus DeCSS program to Unlambda. Though more likely it'll just make me really confused :)

Pessimist!

[Egonis]

Well, for someone who doesn't really care about such "unimportant" things, you sure have put alot of thought into it.

Although I truly don't completely understand what this small-code interpreter's useful application would be... I still respect the everyday advances we make.

On a sidenote, I recall reading in Psychology that people who go particularly out of their way to be pessimistic, claim to be interested in truly masculine things, and drive big SUVs generally have microscopic male sex organs.

Formal Languages and Automata for fun?!?!?

[MonkeyBot]

Man, people who do this for a living scare me. What scares me worse are the people who wrote a compiler called Brainfuck , a language that has 8 operators and emulates a Turing machine. Even more scary are the inventors of Malbolge , a programming language that took over a year to write a "Hello World" program--IN MIXED UPPER/LOWER CASE!!!!

Pi

[jim3e8]

The picture reminds me of the raster image that was found in the digits of pi, in the book Contact. I bet if you looked hard enough you could find his 34-byte universal combinator there. Accident, or not? ;)

Re:Pi

[BitwizeGHC]

Even though Carl Sagan probably intended it to throw a monkey wrench into Arroway's atheism, it has been proven that the number pi has every possible sequence of numbers contained somewhere within it. So yes, the bitmap of the circle is in there, and so is the 34-byte combinator, the ASCII encoding of this message, your social security number, the precise number of licks it takes to get to the Tootsie Roll center of a Tootsie Pop, etc. Pi truly has all the answers. The tricky part is finding them in that morasse of digits.

Re:Pi

[minusthink]

but does pi contain itself? (without the decimal point).

no it's not a stupid question, we're dealing with infinity here. :D

Re:Pi

[delta407]

Pi is a transcendental number, meaining that it is a non-repeating, non-terminating decimal that is not algebraic (i.e. not a root of any repeating or terminating decimal). So, no, pi does not contain itself.

Also, though we can't fully evaluate pi, some guy named Lindemann proved in 1882 that, indeed, pi was transcendental (and that he had way too much time on his hands). More information can be found here, if you want.

Re:Pi

[mindstrm]

I'm a bit lost here.

Just because a number is nonrepeating and infinite does not mean it contains every possible sequence of numbers.

It's like saying that if the universe were infinite, then somewehre there is a planet just like this one, but where my laptop is green instead of blue. It just isn't so.

Re:Pi

[TheOnlyCoolTim]

You are thinking that the universe is truly infinite. It isn't, as far as I've heard. There is pretty much a set amount of stuff that was here from the Big Bang and that's all we have to work with.

There are also multiple-universe theories, in some of which, there DOES exist a planet where your laptop is green, since some of them postulate an infinity of universes for ever possibility.

Tim

Re:Pi

[Pussy Is Money]

There is a problem with these "a universe for every possibility" theories. Where is the universe for the possibility that there is only a single universe?

Re:Pi

[Lionel Hutts]

Please provide a reference to this alleged proof that pi is normal.

Re:Pi

[PurpleBob]

Just because a number is nonrepeating and infinite does not mean it contains every possible sequence of numbers.

What you say is true.

However, pi goes beyond that. It is conjectured (as far as I know, not yet proven) to be a "normal number", which means that it does contain every possible (finite) sequence of integers.

Re:Pi

[Alsee]

There is a problem with these "a universe for every possibility" theories. Where is the universe for the possibility that there is only a single universe?

Simple. If the theory is true then "only a single universe" isn't a possiblity.

You are confusing "imagining a possibility" with "physics allowing a possibility".

-

Re:Pi

[Pussy Is Money]

Well, that's an answer. But how about the possibility of the theory being false? How about the possibility of the theory being false in some but not all possible universes?

The problem isn't in the nature of the universe. Its in the nature of possibility.

Re:Pi

[Alsee]

How about the possibility of the theory being false in some but not all possible universes?

Nope. It's true or it's false.

The problem isn't in the nature of the universe. Its in the nature of possibility.

As I said, the problem is in how you are interpreting "possibility". You are confusing "imagining a possibility" with "physics allowing a possibility".

The "universe for every possibility" theories say that everything that is possible actually exists. Saying "how about the possibility of X" does not mean X is possible.

-

Re:Pi

[Pussy Is Money]

Precisely. The question is how many possible universes physics allows. The problem with the theory is that it is far from obvious how it is possible for one universe to differ from another universe if not by physics. How can two universes be different if their physics do not differ?

But if you accept that physics may differ, then you lose the requirement that all possibilities must be allowed by physics: after all, there is no longer "one kind of physics". Instead, there may be many differing kinds of physics, and you lose that particular defense against the inconsistency I previously mentioned. I think.

Re:Pi

[Alsee]

Use planets as an analogy. They can have different mass, temperature, composition, etc. but there is a higher level set of rules/order from which they form. Some numbers will have an arbitrary value (gravity = 32 feet per second per second), but some rules are fixed gravity = G * M1 * M2 / D^2.

If you can figure out the higher level laws governing the creation of the universe then you could figure out the extent and limits of what else is possible.

-

Re:Pi

[Pussy Is Money]

Well, I suppose. But I am still confused. To use your analogy, do the planets in our universe constitute all possible planets? Why or why not?

Re:Pi

[Alsee]

do the planets in our universe constitute all possible planets? Why or why not?

No. The universe is finite, and there are many planet variations that are posible but never happened to occur. We have some general idea what is possible and what isn't.

Back to the the multi-universe theory there would be two variations on the theory. One where, like planets, some random collection of possible universes happen to occur. In another variation of the theory every possibility occurs.

They are certainly interesting theories, but there is very little evidence yet weather they are good theories or bad theories. This stuff goes pretty far beyond the hard evidence to back it up. It's partly just a game of making stuff up, then seeing if it is logicly self-consistant.

Alot of this stuff traces back to the particle/wave duality of light. If light can take two paths, and you look, it always takes exactly one path like a particle would. If you don't check which path it takes, you get proof that it takes both, like a wave would. One of the only explanations for this that seems to make any sense is that everything that can happen does happen. The universe splits. In one it goes left, and in the other it goes right. The two basicly identical universes curve a little bit apart, but then come back together at the same "spot". The two different versions of the same particle interfere with each other. The math of it works out exactly right. In physics, if the math works then you've probably got the right explanation.

It's a pretty far fetched thing to imagine and most scientists are quite sceptical. The thing is, quantum mechanics has some *truly* bizzare features and so far this is about the only theory that makes any sense. It's a choice of "far fetched theory" or "we have absolutely no clue".

-

Re:Pi

[Pussy Is Money]

It is fascinating stuff and I do not entertain the notion that a layman's understanding such as my own can add much to the discussion of the physics behind the theory. I have to admit that the results in themselves are interesting enough to warrant consideration of strange creatures like multiverse theory.

From another point of view, however, the notion of "all possible worlds" makes very little sense. All the possible worlds that could conceivably be constructed by applying the rules of physics (but then what is it that creates the differences between repeated applications)? All possible worlds that God had the time to create? All possible worlds that fit on the tip of a needle?

Clearly some or all of that is nonsense. But by whose authority do we determine which one (assuming that there will not be any empirical means to verify any kind of multiverse theory for some time to come)? So I am a bit skeptical. When "we have absolutely no clue" is closer to the truth than "far fetched theory" then it strikes me that "we have no clue" is, well, closer to the truth, even if it is less productive.

But I understand that the mathematical results are very compelling. It would be very interesting to see it established that the creation of something profound like an entire universe were dependant on it being allowed by mathematics. It would be the ultimate triumph for maths, I think.

Don't laugh...

[Lictor]

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.

Re:Don't laugh...

[jcupitt65]

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

I LOVE my universal machine

[Anonymous Coward]

As soon as I saw it in the back of the latest Spider Man comic, (on the back of the page which advertises X-Ray specs, which by the way, don't really work, trust me, save your cash!) I just knew I had to have one. It took me all summer saving up the money for one mowing lawns, collecting bottle caps, and painting fences. But all that hard work paid off, during the last week of August, when I got my shiny new Universal Machine in the mail.

I remember like it was yesterday how my hands trembled, as I tore the wrapping off the box. Sweat dripped from my face and stung my eyes in the mid-afternoon heat, as they had so many dusty days of mowing and painting, but it was all worth it!

My Universal Machine does EVERYTHING! I set it in my pet hamster's cage, and it exercised Herbie (my hamster) till he was tired and sleepy. I then took it out and used it to clean the dishes and take out the trash (my chores) which it did AUTOMATICALLY!

Then, as the sun was setting, I used my Universal Machine to walk Sparky (my dog), which it did all by itself. It even cleaned up after him. I was amazed!

When school started, I used my Universal Machine to do my homework, which it did with no intervention from me! Then, my friend Bobby and me used it to make two fake ID's and disguises to get us into an R rated movie... there's nothing it can't do!

I used to love using it to scare my older sister and her stupid high-school friends, or chase the neighbor's cat up and down the street. Now, mostly I let my Universal Machine do everything for me, since it's universal, it can do anything and everything, and since it's a machine, it never gets tired or bored or complains.

In short, I wholeheartedly recommend the Universal Machine to anyone who wants a machine which is universal. It even processes S and K commands. It does absolutely EVERYTHING.

Sincerely,

Timmy B. Stevenson
Atlanta, Georgia

Yeah, but what about the universal program?

[AJWM]

I mean, nowhere on that page did I see how you'd write "Hello World!".

one-combinator basis for Lambda-terms

[Traa]

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.

Re:one-combinator basis for Lambda-terms

[Pseudonym]

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.

SSSCA

[rarose]

Just think folks... these 34 bytes would be subject to the SSSCA. Which means it would be illegal unless it incorporated another 3 megabytes of protection.

Another example of how unrealistic the SSSCA is.

ARGHGHH!

[Skim123]

Here I am, taking a break from studying for my Programming Languages final, so I meander on over to /. and see: LAMBDA CALCULUS and COMBINATORS, the same stuff I've been studying for the last few hours. Sigh.

SKK this.

Re:ARGHGHH!

[bentini]

cs258?
(you'll know what it means if it applies to you).

Re:ARGHGHH!

[Skim123]

Nope, CSE 230

Lambda Calculus wins again!

[Tom7]

More proof that lambda calculus IS the fundamental model of computation, NOT turing machines.

Now, which one is your favorite programming language closer to? ;)

Re:Lambda Calculus wins again!

[William Tanksley]

This seems to prove that the biggest part of lambda calculus isn't needed, doesn't it? Hardly a "win".

I do like combinatorial calculus, though; especially in non-applicative form. You know, the form where functions don't get applied to their parameters; instead, functions get applied to the stack, which contains the result of previous functions. (That is, function composition becomes the fundamental operation.) Lots of interesting results.

Currying is also interesting, but is more studied :-).

-Billy

Re:Lambda Calculus wins again!

[Tom7]

> This seems to prove that the biggest part of lambda calculus isn't needed, doesn't it? Hardly a "win".

I don't know what you mean. All I'm saying is that the lambda calculus is a simpler and more foundational model of computation than turing machines. The fact that we can distill the essence of computation down to two closed lambda terms is a positive result!

In simple terms yes..

[RandomInAction]

..the sinclair could add up any, given, number of numbers.

Re:In simple terms yes..

[PD]

Can the sinclair add up so many numbers that it overflows? Can the sinclair add two billion digit numbers? It can't hold the two starting numbers, and it can't hold the sum.

Re:In simple terms yes..

[RandomInAction]

If you are prepared to sit next to it managing it's input and output(ie tapes) it could anything up with out an overflow. A Turing machine doesn't need to hold an initial set, that's on the tape. It manipulates symbols on the tape to generate an output. A Sinclair could be programmed to do just that. A Sinclair could add 2 or 100, billion digit numbers. Not in memory of course; but by using tapes. I'm not sure that I'm getting that this across.

Re:In simple terms yes..

[PD]

If you are prepared to sit next to it managing it's input and output(ie tapes) it could anything up with out an overflow.

Then you're not talking about a Sinclair. You're effectively saying that the combination of a tape feeder monkey AND a Sinclair are a turing machine. That's quite a bit different than just a Sinclair.

A Turing machine doesn't need to hold an initial set, that's on the tape

The tape is defined as part of the turing machine. A Turing machine without a tape is just an automaton

I'm not sure that I'm getting that this across.


Yes, you are. You're adding all sorts of hardware to the sinclair to make it more capable, but remember that even a sinclair with a googalplex bytes of memory is infinitely smaller than the tape on a Turing machine.

Let me help you out:

Given that you have a Sinclair programmed to emulate JUST the read/write head, you also need to have an INFINITELY long mag tape to store the initial program/dataset and hold the result of the computation.

Only that will make a machine equal to a Turing machine, nothing else. A Sinclair by itself is not equivalent. That infinite tape is very important.

To give you an insight into the different, let's consider the halting problem. It's impossible to write a program that can determine if a Turing machine will ever stop running. BUT, I can easily imagine a program that can tell you if a Sinclair will ever stop running.

Step by step:

1) A sinclair has a finite memory (1K?) and a finite number of processor registers and states. If one desired, one could enumerate them all, from 1 to N.

2) Now, we know how many states a Sinclair has. We also know how quickly the machine changes states (the clock speed).

3) The only thing else that we need is a computer larger than the Sinclair, large enough to hold all possible states of the Sinclair. That larger computer has access to the complete state of the Sinclair computer.

4) We load the Sinclair with our mystery program. Does it stop or not? We will soon know the answer.

5) At every clock cycle, the larger computer stores away the complete state of the Sinclair computer.

6) The larger computer also checks the just stored state of the Sinclair computer against all the past states that have already been observed. If there is a match, that means that the Sinclair is in exactly the same state that it was in sometime during the past. Therefore, the Sinclair is in an infinite loop and will never stop.

7) Since we know how many possible states the Sinclair could be in. We also know the clock speed of the Sinclair. Therefore, we know what the maximum run time of the Sinclair is without ever duplicating the state of the machine.

8) So, with the information from #7, we can positively say that if a duplicate state is not detected (as in #6) then the Sinclair's program will eventually halt.

So, there's the proof. The halting problem is impossible to solve on a Turing machine. I have just solved it for a Sinclair, therefore, a Sinclair is not a Turing machine.

Add the infinite tape to the Sinclair and it WILL be a Turing machine. (If you can find an infinite tape I will buy it from you for a million dollars.)

Re:note: OmniWeb should not be used

[SirRichardPumpaloaf]

You can use more than one browser, you know. I use Omniweb for most things, and if I need better CSS/javascript support I fire up IE for that site. It's a program, not your wife. Be promiscuous and happy! :-)

For all the braintrusts posting smaller solutions

[Jerf]

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'm waiting for the NetBSD port

[jgp]

.. and I have an infinate spool of paper tape for swap ...

dude

[honkycat]

Lighten up, Francis!!

Re:Crash the VM.....

[MillionthMonkey]

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.

Simple language? Ook!

[CTho9305]

Ook!

I thought

[Rhinobird]

I thought the simplest language was brainfuck...what with it's 8 commands: , . + - [ ]

another Plain English translation?

[klez23]

I haven't given it much thought at this juncture

to head off the inevitable questions, at this juncture == "yet".

I Could Have Sworn...

[Baldrson]

...that it was a Universal machine in 371 Bits not 272 bits, but then the links are gone and I'm too lazy to download Ghostscript on this #(&*$ Window's box.

Re:For all the braintrusts posting smaller solutio

[ariels]

That's not a problem, of course. Here's how you code in ARIELSOL: Unless you want to use the "UTM shortcut" (patent pending), just write out your program in ISO standard C. If you decide to take advantage of my NEW! UNIQUE! "UTM shortcut technology", your program should be the single bit `0' (note that this is not a legal C program).

The ARIELSOL interpreter (forthcoming) either compiles and runs your program as though it were a C program (if it's not the single bit 0), OR, if it is the single bit 0, runs itself on the input. Voila! Universality guaranteed, and in the same encoding.

I therefore claim that ARIELSOL encodes its universal machine in a single bit.

(I also claim that there is no Nobel prize in mathematics...)

Re:For all the braintrusts posting smaller solutio

[cameldrv]

This is one possible definition, but it's hardly the only interesting one. Lots of people have worked on Turing Machines using minimal numbers of states and symbols which are universal under very convoluted encodings. Requiring the "same" encoding may not be possible, for example in the Turing Machine case, there is no definitive simplest encoding from a set of symbols on a tape into a state table. Therefore by your definition, it is impossible to make a Universal Turing Machine.

S-K++

[supersnail]

Language enchanced with the addition of the "U" and "C" instructions.

Re:For all the braintrusts posting smaller solutio

[Pike65]

I can beat that. (Score:5, Funny)
by MWoody on Monday March 18, @06:20PM (#3183711)

* * *

For all the braintrusts posting smallers olutions (Score:3)
by Jerf on Tuesday March 19, @03:15AM (#3184909)

* * *

I guess the moderators have spoken. And they have a sense of humour.

Re:For all the braintrusts posting smaller solutio

[Jerf]

Go back to that section in theory class and pay closer attention, please; you'll find the section starts by defining an encoding of a TM, usually with only 1's and 0's, using the sequence of 1's as values and 0's as punctuation.

Re:For all the braintrusts posting smaller solutio

[Jerf]

Yeah. Check again. ;-)

And besides, you're leaning on Slashdot moderators for support in a mathematical argument? I get victory by default. (Oddly, Slashdot seems better with legal arguments then real Computer Science...)

Re:Crash the VM.....

[MillionthMonkey]

That's more likely because of MS subtly changing stuff in IE to break Java every release than some fault of Sun's. Java 1.4 applets in Konqueror and Mozilla are rock-solid on my Linux system.
Yes, you're probably right- that does make a lot of sense. Mozilla doesn't have this problem on either OS. Except this version of IE was only updated last year and I downloaded Sun's new 1.4 J2SE SDK last week.
I suspect it's a combination of Microsoft playing games with the rendering components, and Sun being too busy coming up with new APIs instead of fixing the ones people are already using.

Re:For all the braintrusts posting smaller solutio

[BoBaBrain]

There isn't a nobel prize in mathematics. Story has it that Alfred Nobel's wife ran off with a mathematician.
And to think, we were that close to getting it. :)

Er

[greenrd]

The encoded UTM much accept other Turing Machines in the same encoding.

Who says?

It's still a valid point.

Re:Er

[Jerf]

If it can't accept other Turing Machines in the same encoding as itself, it's hardly a Universal Turning Machine, is it?

Oh, I'm sorry, am I dissing other people's opinion on this mathematical issue? How non-post-modern and non-PC of me. If all these people think it, despite clearly not understanding what's going on at all, then it can't help but be mathematical proof, no?

Re:Er

[greenrd]

Firstly, that's rubbish:

This is why we instroduce the notion of a universal turing machine (UTM), which along with the input on the tape, takes in the description of a machine M. The UTM can go on then to simulate M on the rest of the contents of the input tape. A universal turing machine can thus simulate any other machine.

A UTM could be in principle implemented in hardware (but not in practice - a UTM cannot be implemented in practice, period). In this case it would not make sense to require that the encoding of its input was the same as the encoding of itself, since this UTM is not a program, it's a device!

Secondly, I thought SK was functional and the Turing machine is imperative? Non-trivial paradigm mismatch here?

Re:Er

[Jerf]

You did not understand the material in the posted link, probably because it's referencing by implication a whole lot of other work. The UTM is both a program and a device, inasmuch as there's a differnce in CS theory anyhow; that's the whole damned (recursive) (brilliant) (mind-bending) point. As these are mathematical concepts, arguments based on word games ("is not a program, it's a device!") are generally fruitless. You're going to have to forgive me if I again wave my hands toward CS theory classes/books; this stuff generally consumes multiple chapters and multiple weeks repectively, and your average CS grad still doesn't quite get it all. I can't correct that in a Slashdot posting, no matter how many people try to post.

(Heck, a non-trivial number of the grad students find this stuff extremely challenging, and curse those of us who find it comprehensible. (Not easy; I don't know anyone who finds this stuff "easy". But comprehensible.))

TM's are really neither functional nor imperitive, nor OO or anything else. It's the bottom, the foundation upon which those paradigms are built. (Remember, there's really no such thing as a "functional" language in the sense that the language requires functional constructs, and rejects all else. It's just that there are languages that encourage functional programming techniques. As long as the language is Turing Complete, you could always implement a TM on top of the base language, then program in whatever style you want, albiet with potentially huge losses in efficiency.) The traditional TM may look imperative, and the SK machine may look functional, from certain points of view, but they are the same thing. The exact same thing. Isomorphic. Identical. Synonymous (that's probably the best way of thinking about it). Again, that's the point.

Re:For all the braintrusts posting smaller solutio

[cameldrv]

I'm well aware that there are encodings from turing machines to bits. My point is that, given the definition of a Turing machine, there is no one single canonical encoding that is objectively correct. Similarly, there are an infinite number of correct ways to encode any type of graph. Just because your textbook defines one way does not mean that it is the only way.

Re:For all the braintrusts posting smaller solutio

[Jerf]

True, but you still have to define something, a point lacking in all rebuttals and all the clever postings. Calling a single bit the UTM still requires a lot of fleshing out, and I think it will result in some infinitely recursive requirements for special cases in the UTM; in other words, it's impossible. But then, the burder of proof isn't on me, it's on everybody who seems upset that mathematics doesn't bend to their whim.

Note that it is provably impossible to know we have the smallest possible UTM... but 1-bit it ain't.

The Mind of the Machine.

[metacell]

I put you among my Friends just for mentioning Haskell.

And I thank God that there isn't any programming language based on the Turing machine.

No, wait, there is... Assembler!

Re:The Mind of the Machine.

[Uller-RM]

Heh - they actually have offered entire classes on Haskell and functional programming in the past at UP. Try writing a console game in Haskell sometime - it's fun :)

No.. you missed the point.

[mindstrm]

The point is, just because you have an infinity does not mean all possibilities are covered.

WEhther you want ot call it an infinite universe, or an infinite number of finite universes, it still does not mean that every possibly thing exists.

Take the set {1,2,3,4,...} . WE can say that every whole number exists in this set.
However, an infinite set of the same size
{1, 3, 5, 7, 9, ...} does NOT contain every whole number. Both are infinite, and both of the same size.

Re:For all the braintrusts posting smaller solutio

[bentini]

This would be so much truer if Alfred Nobel had had a wife, huh?