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 ."
They occasionally tinker with `programming systems', but those are so high level that they hardly count (and rarely count accurately; precision is for applications.)
Loneliness is a power that we possess to give or take away forever
> 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>)
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
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.
"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"
Sig went tro...aahemmm.....fishing........
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.
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!
cpeterso
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.
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.
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
yup... didnt even stand a chance...
The server was probably running at a bandwidth of 34 bytes.
Remember "Bring 'em on"? *sigh
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''
0xC3
- 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.
--
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.
If tits were wings it'd be flying around.
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()
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.
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
Irritable, left-wing and possibly humorous bumper stickers and t-shirts
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.
If tits were wings it'd be flying around.
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.)
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.
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
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?
20 January 2017: the End of an Error.
I mean, nowhere on that page did I see how you'd write "Hello World!".
-- Alastair
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
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.
N4st0r, trixx0r h0bb1tz0rz! Th3y st0l3 0ur pr3c10uzz!
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.
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.
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.
--Rob
SKK this.
I could not justify my existence if I were a turkey farmer. Would I terminate myself? Undoubtably, yes.
More proof that lambda calculus IS the fundamental model of computation, NOT turing machines.
;)
Now, which one is your favorite programming language closer to?
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
Omnia vestra castrorum habetur nobis.
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.
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.
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.)
"Biped! Good cranial development. Evidently considerable human ancestry."
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.
Win dain a lotica, en vai tu ri silota
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.
...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.
Seastead this.
Old COBOL programmers never die. They just code in C.
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".
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
A Turing machine is a machine that uses a tape, a read/write head, and a set of rules to solve an equation.
... x1000000000000)
The equation that I wish to solve has a trillion arguments:
f(x1, x2, x3,
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.
If tits were wings it'd be flying around.
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.
If tits were wings it'd be flying around.
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.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
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.
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...)
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.
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.)
If tits were wings it'd be flying around.
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?
Secondly, I thought SK was functional and the Turing machine is imperative? Non-trivial paradigm mismatch here?
Female Prison Rape in NY
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.
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.
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 s_k)
String f(String s1, String s2,
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.
So a Universal machine would be anything that implements a language that is Turing complete, of which a Turing machine is an example, no?
Donate background CPU time to fight cancer.
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.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
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".
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
The point is, just because you have an infinity does not mean all possibilities are covered.
...} does NOT contain every whole number. Both are infinite, and both of the same size.
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,
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 :)
This would be so much truer if Alfred Nobel had had a wife, huh?