Wolfram's 2,3 Turing Machine Not Universal

Fishbat writes "In a cutting message to the Foundations of Mathematics mailing list, Stanford's Vaughan Pratt has pointed out an elementary mistake in the recently announced proof that Wolfram's (2,3) machine is universal." Update: 10/30 04:18 GMT by KD : Ed Pegg Jr. from Wolfram Research points to this response to Dr. Pratt's note, which has been submitted to the FoM mailing list but has not yet appeared there due to moderation.

Comments

The Filter

[eldavojohn]

The author of this e-mail, which is incredibly insightful and articulate asked:

How did an argument containing such an elementary fallacy get through the filter? To be fair, I don't consider this that elementary a fallacy but when you break it down to if x + y = infinity then both x & y are infinity it does sound like a rather obvious pitfall. And, in response to his comment on catching it, it had not yet been through "the filter" as the original story stated:

Smith's proof will be published in the journal Complex Systems. Meaning it had not yet been peer reviewed. But I agree with the author however abrasive he came off (although this is far higher than an elementary mistake) when he said:

Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution? I can forgive an undergrad prof for missing this, his response was probably just to look at it and encourage the kid to submit it. Afterall, what motive would a professor have to read it?

But what should really be noted is what Wolfram himself is quoted as saying from the initial publishing of this proof:

"I had no idea how long it would take for the prize to be won," said Stephen Wolfram. "It could have taken a year, a decade, or a century. I'm thrilled it was so quick. It's an impressive piece of work." Alright, that last sentence there is pretty damning. I have heard time and time again on Slashdot that Wolfram just took other people's work, that he had people working underneath him & that he didn't actually know what he was talking about in his book. This is some corroborating evidence, in my opinion.

I don't know a lot about finite automata but this whole display has shown that Alex Smith is talented but not the winner of the prize, it's best to accept and seek out all criticisms from your community before publishing & Wolfram is not the genius he makes himself out to be. I don't believe I will ever read "A New Kind of Science" as I have many other books in front of that one on my list.

Sounds like just another step in the learning process for Alex--too bad about the cash but he is only 20 and from the looks of it has a bright and promising future. Quite the embarrassment for Wolfram, however.

The real kicker would be if Wolfram had asked his staff to review the proof and they knew it had an elementary mistake and had told him it was golden. Now that would be poetic justice.

Re:The Filter

[Anonymous Coward]

You misread the post. He said that if x + y = infinity and y is finite, then x must be infinity. This is TRUE for numbers. You cannot apply this by analogy to automata and think it is still true. It is not.

Re:The Filter

[jnana]

Indeed. A prior email in that thread -- by the same author, Pratt -- makes it very clear by giving the example of 2 pushdown automata (PDA). A single PDA by itself is not universal, but the system comprised of 2 PDAs is universal, since each stack can represent one side of the Turing machine tape.

As Pratt states, the fallacy is of the following form: a system comprised of 2 PDAs, PDA A and PDA B, is universal. PDA A alone is not universal. Therefore, PDA B must be universal (because the system as a whole is universal). QED.

Of course, in the actual proof, it was not 2 PDAs, but a 2,3 machine and an encoder (i.e.,"PDA A" == "encoder" and "PDA B" == "2,3 machine").

Re:The Filter

[Anonymous Coward]

Incidentally, for anyone who wants to learn something about automata and theory of computation and doesn't know where to start, I highly recommend the following book by Michael Sipser: Introduction to the Theory of Computation.

It's quite pricey for such a small book, but it's worth its weight in gold (i.e., the time you save by reading this little masterpiece instead of something else that's less well written). You can find the 1st edition used for much cheaper than the 2nd edition, and the differences between the two editions are pretty minor.

p.s. I have no connection to the book or the author. I'm just a very happy customer.

Re:The Filter

[EveLibertine]

Regardless, the guy that wrote that email is a prat.

Re:The Filter

[phiwum]

Smith's proof will be published in the journal Complex Systems. Meaning it had not yet been peer reviewed. On the contrary, if a result "will be published", then there is every reason to believe that it has been peer-reviewed.

One doesn't use such positive language prior to peer-review. If it hasn't been reviewed, there's very little reason to suppose that it will be published in the journal to which it has been submitted. (Indeed, as I recall, Wolfram formed a respectable group of scholars for reviewing this and other arguments for this proof and thus it had been reviewed.)

Re:The Filter

[Anonymous Coward]

"p.s. I have no connection to the book or the author. I'm just a very happy customer."

Hey Michael, long time no post.

Re:The Filter

[wasted]

Smith's proof will be published in the journal Complex Systems.

Meaning it had not yet been peer reviewed.

On the contrary, if a result "will be published", then there is every reason to believe that it has been peer-reviewed.

My understanding was that the purpose of publishing is peer review. Once published, a peer can replicate the methods and obtain the same results, (or not,) see the process, logic, and methods, and agree or disagree with the findings. Is my understanding wrong?

Re:The Filter

[Anonymous Coward]

Prior to being accepted for publication, a paper is sent to (presumably) experts in the field to review the paper to make sure the research is worthy of publication. That's what is meant by "peer-reviewed" journals.

Re:The Filter

[noidentity]

I'm not conversant in the terms, but a simplification of this flawed logic seems to be this: this machine made of parts A and B exhibits a new behavior that is not exhibited by part A, therefore it must be something part B exhibits on its own as well. But when building machines, the sum can be more than the parts. After all, that's the whole point of this, to find the minimal parts that implement a universal Turing machine when put together. But as I said, this isn't my field so the error may not be this fundamental.

Re:The Filter

[SiliconEntity]

His analogy is interesting but I'm not sure he is exactly right in describing the nature of the proof.

My understanding is that the proof shows how to set up the machine so that it will execute any calculation - it will be "universal". However the question mark is that in order to do the set up, you have to prepare an infinite sequence in memory just a certain way. The question is whether that set up operation is universal itself, in which case the fact that the whole operation is universal wouldn't count - because you would have used a universal step as part of the construction.

The proof shows that the set up operation is not universal, so that removes the loophole. Therefore since the set up can be done without the power of universal computation, there is no more obstacle to the conclusion that the final computational step is universal.

That's how I thought the proof worked. It's not exactly that the whole machine is universal, and the setup is non-universal, therefore the calculation is universal. Rather, it's that this is a way of doing a universal calculation, and we just had to make sure the set up was kosher. If my understanding is correct then the objection does not apply and the proof still works.

Re:The Filter

[HeadlessNotAHorseman]

Wolfram's 2,3 Turing Machine Not Universal
HOLLYWOOD - In a shock move, MGM has undercut Universal in its bid for the movie rights to Wolfram's 2,3 Turing Machine. Insiders had predicted that Universal would make the deal to build on the phenomenal success of Wolfram's 2,2 Turing Machine, but it has since become apparent that Universal failed to include an option for all sequels in the original contract. The exact figure offered by MGM is unknown, but is believed to be approximately x + y, and we can confirm that y is a finite number. More details will follow.

Re:The Filter

[djupedal]

"My understanding was that the purpose of publishing is peer review."

And how many 20 year olds run out and buy the latest copy of 'Complex Systems'...?

Not enough, apparently :)

Re:The Filter

[deepvoid]

By stating a Turing machine is universal, one is saying that the machine can handle the entire spectrum of possible inputs, something the Turing machine in the document clearly does not. By stipulating that the inputs are by some arbitrary rule finite (in the sense that the writer would want to restrict the initial conditions even a little), the universal nature of the test is eliminated and thus becomes yet another of the countless examples of failed attempts at Turing completeness.

Sorry, good try, maybe next time?

Re:The Filter

[Workaphobia]

> "This is TRUE for numbers."

Eh, my instinct is to twitch when we're so callously applying the addition operator to objects that are not natural numbers (or reals, etc). Maybe there's some definition or convention I'm unaware of, but I'd restate that as:

"If the set A union B contains an infinite number of elements, and B contains finitely many elements, then A's cardinality must be infinite."

But even that I'm not too sure about, as I know there's a lot more than meets the eye when it comes to set theory.

Re:The Filter

[Workaphobia]

Am I correct in thinking that the issue is that the given proof proves that the wrong system is universal? I read part of the proof but I'm unfamiliar with some of their terminology and models. From what I can tell, the question was whether a particular Turing machine was universal, and the answer was "yes, with some minor modifications", and the prize panel decided that this adaptation fit within the definition of the problem.

Re:The Filter

[Workaphobia]

You jest, but it's a damn good book. I actively felt, as I was reading it for my Models of Computation class last semester, that it was the best textbook I've had up to that point. It's very precise.

Note that I'm not anonymous.

Re:The Filter

[ais523]

This argument and Pratt's argument that the universality proof are incorrect both share the same flaw; see the response linked in the update of the original story for more details. Yes, a system consisting of two push-down automata that can communicate back and forth is universal. However, the proof of the universality of the 2,3 Turing machine in question doesn't set up a system where two systems can communicate back and forth; instead, the output of one is used as the input of the other, and there is no communication in the other direction. If one PDA is used as an encoder for another, the resulting system is not universal. The definition of universality in the original prize that was agreed on by the judges basically said that in the case of obviously simple encoders, if an encoder+system together are universal than the system itself is. The encoder used in the proof is not obviously simple (as it takes up several pages in the proof) but is clearly not doing any sort of universal calculation itself or engaging in part of such a calculation.

The real problem here is that with other definitions of 'universal', the system might indeed not be universal; the definitions are important in such cases. (For instance, a definition that restricted the initial condition to be finite and surrounded by nothing but yellow on the tape would result in the system being non-universal, but this definition is too restrictive to be useful.) Changing the definition of 'universal' is likely to result in changes to what is universal and what isn't, although it seems likely that the 2,3 Turing machine in question is well on the universal side of that edge (although not as far as some other systems). Even systems such as rule 110 that are generally accepted to be universal would be non-universal if a non-repeating finite initial condition was mandated by a definition of universality.

So in short, nothing has been disproven, the machine is still universal, and the headline is wrong.

Re:The Filter

[kripkenstein]

Smith's proof will be published in the journal Complex Systems. Meaning it had not yet been peer reviewed. No, this means the opposite AFAIK. If it will be published in a peer-reviewed journal, then it has already been reviewed. Otherwise you would say it has been submitted to the journal, which would imply a review is pending.

That is, you only say it will be published after acceptance by the journal, following peer review. It is then published some time later, depending on the queue for publication in that journal.

Re:The Filter

[phiwum]

The purpose of publishing is to make the article available to peers, so you are right that there is the opportunity for review after publishing. But prior to publishing, the article will be reviewed by the editor and two or three anonymous reviewers and this process is commonly referred to as "peer review".

Re:The Filter

[jnana]

I didn't understand Pratt to be arguing that the 2-PDA system is directly analogous to the proof system in the way that you state. What I understood Pratt's point to be was that the proof does not prove that the 2,3 machine must be universal, since it is entirely possible that while the encoding mechanism itself is not universal, it nevertheless could be sufficiently complex that universality does not (and perhaps cannot) exist without it.

The author of the proof states on page 26 (counting the first PDF page as 0) the following:

Therefore, this algorithm for determining an initial condition, whilst somewhat complicated, is definitely not itself universal, and so the universality discovered above is a property of system 0, and not of the algorithm used to find its initial condition.

I took Pratt to be arguing that this is not a valid inference, that one can't just say that because the encoding and creation of initial condition mechanism is not universal, while the system as a whole is universal, that the 2,3 machine is therefore universal.

I'm looking forward to learning more over the next few days, but that is what I meant by earlier post. I may have completely misinterpreted Prof. Pratt's criticism, but that's my take on it.

P.s. Prof. Davis stated on the FOM list that the committee has not actually ruled that the paper is acceptable yet. Apparently, people within Wolfram's organization were the ones who made the determination. Given that, I'm not sure that it's correct for you to state that "the machine is still universal", since the paper hasn't been peer-reviewed by even the expert peers on the committee, let alone the wider community, and so its universality is still far from established.

Re:The Filter

[ais523]

Whether this is a valid inference depends on the definition of 'universal'; the problem here is that Pratt appears to be using a different definition from the one that the prize committee and the proof adopt. The inference may be incorrect with certain definitions of 'universal'; however, it is correct with other definitions. My point is that the counterexamples that Pratt gives to the inference are incorrect; that does not, of course, mean that the inference itself is correct, but it means that looking into where the problems with the counterexample came from is worth doing, and it appears to be a misconception between systems interacting backwards and forwards, and preprocessors. It seems to me that most general definitions of 'universal' will cause the inference in question to be correct (there is at least one definition which includes the inference as part of the definition itself, that is 'A system is universal if it can emulate any Turing machine if given an appropriate initial condition encoded using a non-universal system', although there is some circular reasoning involved in that definition).

Re:The Filter

[xHeliosx]

"This bores me. How about a game of basketball?"

Re:The Filter

[The_Wilschon]

Add to that that the intersection of A and B is empty, and I think you'll be ok. Maybe. Of course, it isn't 9am yet, and I have a midterm in an hour, so maybe I'm just screwed up here. (I'm reading slashdot for a short break)

Re:The Filter

[Jim Starx]

Your statement on set theory is completely correct and mathematically precise. The statement about the addition of infinite numbers is also correct and can be made mathematically precise with limits. But limits are essentially a very painful way of making what we think of as an intuitive notion precise, which is why once we've proven a statement using limits we immidiately stop using limits when we state the result.

Re:The Filter

[Jim Starx]

Not neccesary actually.

Re:The Filter

[JohnsonJohnson]

"I had no idea how long it would take for the prize to be won," said Stephen Wolfram. "It could have taken a year, a decade, or a century. I'm thrilled it was so quick. It's an impressive piece of work."

Alright, that last sentence there is pretty damning. I have heard time and time again on Slashdot that Wolfram just took other people's work, that he had people working underneath him

The charge against Wolfram is that he did not give credit to one of his assistants who proved that a particular 2 state 1 dimensional finite automaton with a neighborhood of 1 was universal. The assistant had also signed a contract that effectively prevented him from releasing the proof on the assistant's own.

& that he didn't actually know what he was talking about in his book. This is some corroborating evidence, in my opinion.

Wolfram's A New Kind of Science makes claims about facts in a wide variety of areas of science especially chaos theory (or nonlinear dynamics or whatever it's called this week) and biology which were either known, discovered by someone unaffiliated with Wolfram, or known to be false (the last being Wolfram's doomed program of a TOE based on network automata). Most of these problems arise from the tone of the book which does not make clear what's original about Wolfram's work (aside from exhaustive study of 1D automata and some simply axiom systems not much) and what is a review of other work. That doesn't mean Wolfram doesn't know what he's talking about, he knows quite a bit, but it's hard to parse that from what is conjecture and as in any major work of such length there are errors.

Wolfram is not the genius he makes himself out to be. I don't believe I will ever read "A New Kind of Science" as I have many other books in front of that one on my list.

Wolfram's reputation as a genius rests on his precociousness as a youth (Wolfram was educated at Eton, Oxford, and Caltech. He published his first scientific paper at the age of 15, and had received his Ph.D. in theoretical physics from Caltech by the age of 20.) and some rather esoteric contributions to the field of particle physics. He also did some early and significant (although perhaps not as significant to other practitioners as to Wolfram himself) work on cellular automata and other discrete systems. A New Kind of Science was Wolfram's attempt to leap from being a bright but unknown outside of his field physicist/mathematician (eg. Ed Witten although since Wolfram didn't publish anything between the early 80's and 2004 or so the comparison is probably unfair to Witten) to Newton, Einstein, or at least Gauss or Euler levels of fame. He failed, but that doesn't mean there is no value in the book, it can serve as a launching point into various not otherwise popular fields of study. I recommend keeping the criticism of the book by area experts close at hand but the book itself can provoke questions and interest in non-experts although it's probably of little value to experts (as compared to the length of the tome).

Re:The Filter

[mightybaldking]

You are perfectly correct given the layman's imprecise use of mathematical language. That is, you understand the concept quite well, but are using the language imprecisely. x + y = infinity is not a valid statement. Nor is x = infinity. infinity is not a number. Infinite is an adjective that can be used to describe a number that you might think of a infinity. In other words, infinity has no value, and can't be "equaled" You would be more correct to say (X + Y) is infinite, or produces a non-finite result. Anybody doing number theory will use set theory and cardinality (look up a few posts) to be completely precise. Even in calculus, where infinity is used more frequently, we really mean "The value of X approaches the infinite"

Re:The Filter

[wizzard2k]

I had the first edition for a class a few years ago (the black book), and it stands out in my mind enough to remember it as informative.

Re:The Filter

[slashdotmsiriv]

"Smith's proof will be published in the journal Complex Systems.
Meaning it had not yet been peer reviewed. "

If it was decided that it will be published, his proof had been peer-reviewed. First you get reviewed, then published.

"Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?"

Something else that strikes me as weird is how come although they were so confident about their result they did
not submit to a more reputable journal than Complex Systems (e.g Computational Complexity and several others of the kind).
It seems that the authors themselves knew that their proof would pass a rigorous peer review.

Re:The Filter

[gedhrel]

No. It means that any Turing machine is expressible and can be simulated by the UTM. Smith's encoding of the target TM is not finite but doesn't require universality in the encoding process.

Whether you consider that to be a UTM in the strongest sense depends on your definition of universality. Pratt doesn't. I think it's debatable but is a question of semantics. The result is still an interesting one: probably more so because of the semantic question :-)

Re:The Filter

[AshtangiMan]

You are correct in layman's terms, but numerically infinite sets do have different values, or sizes, so infinite is not simply an adjective, it does connotate some kind of value . . . for instance, the set of integers is infinite, as is the set of even numbered integers, and the set of prime numbered integers. But these three infinite sets have very different sizes, right? Infinities can therefore said to be "equal to", "less than", or "greater than" other infinities (infinities here means infinite sets). Is this what you refer to above as "cardinality"? I am a layman, and am reaching back to undergraduate logic course where we studied Goerthe's proof of the incompleteness of mathematics.

Re:The Filter

[Traa]

I don't believe I will ever read "A New Kind of Science" as I have many other books in front of that one on my list.

I have very mixed feelings about the book "A New Kind of Science". I did in fact read it and am still upset that such a badly written book (style) might at the same time be one of the few books displaying (but not proving) a key insight that links science and math.

I'm not sure if anyone has managed to get past the 'I'm a genius (read asshole)' parts of the book and filter the little content, and many pwitty pictures, into an abstract that contains the insight that even simple mathematical constructs can hold the wonders that lie between chaos and static/repetitive-states.

Re:The Filter

[dmitrygr]

Well actually the size of even-numbered integers is EQUAL to the size of the set of all integers, since I can create a mapping from elements of one set to the other that will use up all elements in both. A = {set of integers} B = {set of even integers} For all Bi there exists Aj such that Bi = Aj * 2 For all Ai there exists Bj such that Ai = Bj / 2 There...

Re:The Filter

[Dzonatas]

>>> if x + y = infinity and y is finite, then x must be infinity. This is TRUE for numbers. You cannot apply this by analogy to automata and think it is still true. It is not. It is not TRUE for numbers. Both x and y must be infinite for x + y = infinity to be true. Simple as that. If y is finite x is infinity, then x + y = affinity. Simple as that. What's fucked up in the fallacy is that affinity is not a single point, so it appeared to be true in the original if the opposite of the truth was a single number. We know we can not apply it like that (singular | infinite), that is why it is not a single number and it is not infinite. D'oh!

Re:The Filter

[Dzonatas]

>>> if x + y = infinity and y is finite, then x must be infinity. This is TRUE for numbers. You cannot apply this by analogy to automata and think it is still true. It is not.

My bad, I left SPACE out of the equation! lol

It is not TRUE for numbers.

Both x and y must be infinite for x + y = infinity to be true. Simple as that.

If y is finite x is infinity, then x + y = affinity. Simple as that.

What's fucked up in the fallacy is that affinity is not a single point, so it appeared to be true in the original if the opposite of the truth was a single number. We know we can not apply it like that (singular | infinite), that is why it is not a single number and it is not infinite.

  D'oh!

Re:The Filter

[mrogers]

By stating a Turing machine is universal, one is saying that the machine can handle the entire spectrum of possible inputs

No, "universal" means it can simulate any other Turing machine, represented as an appropriately formatted input. It does not follow that all possible inputs are valid representations of Turing machines.

Re:The Filter

[Jim Starx]

What the hell is affinity? I'm a mathematics major and I've never heard that. There's nothing wrong with saying that if x is a finite number and y is infinity then x + y = infinity, at least nothing more then the obvious fact that it's not very precise mathematically. It can easily be made precise by the notion of convergence and there are no surprises when you do so, you get pretty much exactly what you expect.

Re:The Filter

[Bezultek]

"It should be obvious to even the most dim-witted individual who holds an advanced degree in hyperbolic topology."

Re:The Filter

[AshtangiMan]

Perhaps. I seem to recall the size of infinity having something to do with how quickly the set gets there, and the even numbered set gets there half as quickly, so it is a smaller value. Your proof above does not read true to me, in that you state that you can use up all of the elements in both, but you only prove that for each element in one you can map it to an element in the other. Not the same thing, but again this is all 20 years old for me.

Re:The Filter

[volpe]

A single PDA by itself is not universal, but the system comprised of 2 PDAs is universal, since each stack can represent one side of the Turing machine tape.

Pardon my ignorance; it's been a while since I've studied this stuff. But if 2 PDAs can be universal because each stack can represent one side of the Turing machine tape, cannot a single PDA be universal by emulating the pair with a suitably complex alphabet (e.g. the outer-product of the original alphabet with itself)? What have I neglected?

Re:The Filter

[fractoid]

To be fair, I don't consider this that elementary a fallacy... Ah, but don't mathematicians divide all problems into either 'elementary' or 'intractable'? :P

Re:The Filter

[Dzonatas]

I've proved it many times that math alone can not describe a universal machine. You still need a machine to start "the tape", or you still need the machine in order to create that machine. =)

If math alone could describe a universal machine, there is an end. You say a notion of convergence, but I say a notion of the N=NP divergence.

It's an allusion, affinity. Without the bloated notions, infinity - affinity = finite.

The closest way to compute affinity is similar to the discrete wavelet transform. There is no way to compute an analogous wavelet transform because of the space. We can create the allusion of space with a discrete wavelet transform.

infinity - finite = affinity + finite

This is just a simplified version of the more discrete, patented versions. It's too simple to patent -- like obvious.

If you need more proof, grab a map of ionic fields and periodic references. Look at it, and tell me how many dimensions you see. If you still say "there's nothing wrong", then point it out on the chart.

I like math, but I hate it when people make up crazy polluted math just to earn a buck of dumb patents. Well, they are worth their distraction value. lol

Re:The Filter

[JoelKatz]

It is analogous to the question of whether a particular person can solve math problems of a particular type, with some example word problems given. The person does not speak English, so needs a translator to translate the question from English to Spanish. So long as the translator doesn't do any math, the person can solve the problems. If the translator does the math, the person cannot. The question of whether or not the translator does any math may not be simple.

That is precisely what happened in this case. The question was looked into, and it was deemed that the encoder (analogous to the translator) didn't solve the problem but merely translated it into a form the machine itself could solve. Thus, the existence of the encoder proves that the machine can solve the problem.

However, if you disagree about what the encoder does, you will not find the proof convincing.

Re:The Filter

[Jim Starx]

Did you invent this term "affinity" or can you provide a referance? Being a math person it's a pet peeve of mine when people decide to make up math to support their philosophical leanings. Math is definitions and logic, not hand waving and mysticism. If the math doesn't line up with your views you're free to say that math doesn't accurately model whatever system you're talking about; you're not free to make up bad math.

If you would like an example of infinite + finite = infinite just look at the natural number plus 0. {1, 2, 3, ...} union {0} = {0, 1, 2, 3, ...}. In terms of cardinality we have aleph null + 1 = aleph null, thats infinity + finite = infinity.

So yes, the statement IS in fact TRUE for numbers.

Re:The Filter

[geenome]

Mathworld says affinity is another word for affine transform, which of course doesn't make sense here.

Re:The Filter

[mightybaldking]

A = {set of integers} B = {set of even integers} For all Bi there exists Aj such that Bi = Aj * 2 For all Ai there exists Bj such that Ai = Bj / 2

That's a perfectly demonstration of countability.
Countability, in the simplest term means "There is a path I can follow,  that if I keep taking one more step, I'll eventually get there".

Picture an infinitly long hallway, tiled with 12x12 inch tiles.  Are the tiles countable?  That is, if you pick any tile arbitrarily far away, will I eventually get there?
There are two possible paths to take.

1)Follow the left wall, and when I get to the end, I'll turn around and do the next row. -- Not countable, as I'll never get to the second row.
2)Start by going across the hall, when you get to the opposite wall, advance to the next column,  and  continue.  You'll eventually get there.

Now consider an infinite field (infinite in both +-x and +-y directions)
Start anywhere, and spiral outward.  Again, you can eventually get to any point on the field.

Both are countable.

The set of rational numbers (fractions) is countable:

         2
         1
...-2 -1 0 1 2...
        -1
        -2

Fill in the grid as x/y.
Start at 0, and spiral outward (you can eliminate 4/2 as the same as 2/1 if you like).
You will eventually get to any fraction you desire.

All these examples are directly mappable to the set of natural numbers.  All you have to do is count each time you take a step.

That is, the cardinality of the set of natural numbers is exactly equal to the set of rational numbers.

Real numbers are not countable, as there is no "next" number to go to.  That is, if I choose any number (x1) greater than my current position (x), there is another number y| x<y<x1 that falls in between. -- I can never get to two from one.

Re:The Filter

[Dzonatas]

What's made up is the assumption about infinity as presented in the fallacy. What you just simply said is that if infinity already has a set and you add the same set again to it then it still equals *the same* infinity, and that is illogical. No mysticism involved there.

Re:The Filter

[Jim Starx]

Infinity does not "have" a set, that statement doesn't mean anything. Sets have a cardinality, not the other way around. And what exactly do you think is illogical about my previous example? I'll break it down for you:

a) The set {0, 1, 2, 3, ...} has an infinite number of elements.
b) The set {1, 2, 3, ...} has an infinite number of elements.
c) The set {0} has 1 element.
d) The set {0} union {1, 2, 3, ...} is the set {0, 1, 2, 3, ...}.
e) The intersection of the set {0} and the set {1, 2, 3, ...} contains no elements.
f) When two sets are disjoint (no elements in the intersection) the cardinality of their union is the sum of their cardinalities.
g) So card{0, 1, 2, 3, ...} = card{0} + card{1, 2, 3, ...}
h) Thus infinity + 1 = infinity

Now you've said you disagree with (h), I've laid out the reasons why I feel I'm justified in concluding (g). So please indicate what step you believe to be incorrect and why.

Also, I'll ask you again. Do you have a referance for the term "affinity" or did you invent it yourself?

Re:The Filter

[Dzonatas]

Another user here posted a reference to it on the earlier message, did you miss it? I saw it before I posted the last reply.

Re:The Filter

[Jim Starx]

Yes, I missed it, I only skim these forums. So as you haven't objected to any of the points above am I to take it that you've changed you mind and will accept that infinity + finite = infinity?

Re:The Filter

[LandruBek]

Sipser is a great place to start -- and if that whets your appetite, go farther.

His arguments are quite intuitive and approachable, which is great for introducing the subject, but by deliberately keeping the proofs friendly and short, they are not really ``rigorous'' -- and if you want to do research in this area, you've got to learn rigor somewhere else. I learned a lot from Sipser's book, and then I learned a lot more from Hopcroft, Motwani and Ullman's Intro to Automata Theory. (I'd be happy to tell you what, but I don't want to turn this post into a slashvertisment.)

Re:The Filter

[Dzonatas]

If that is how you like to view it, I won't obstruct that view. Why attempt to prove something wrong when it can not even be proven right? My original point remains solid. You are free to make any rough consensus you like, as others are free to challenge it. =)

Re:The Filter

[mightybaldking]

Couple of edits:
That is, the cardinality of the set of natural numbers is exactly equal to the cardinality of the set of rational numbers.,br/> Also, that infinite field is also tiled with those same 12x12 tiles. I can get to any TILE on the field, as they are discrete. Points would be measured in real coordinates, and would not be countable.

Re:The Filter

[BungaDunga]

I always liked Cantor's Proof: http://en.wikipedia.org/wiki/Cantor's_diagonal_argument As I understand it, an "uncountable" infinity has a higher cardinality that a "countable" one, but there is an infinite number of infinities of higher cardinality than the set of integers.

Re:The Filter

[AshtangiMan]

Nicely stated. Ok, I give, and the problem is in treating infinity as a number . . . an easy trap to fall into. Thanks for the explanation.

Ouch

[JoeShmoe950]

I'd hate to be involved in either the submission or the review of that proof. I was rather intriuged when the proof was first posted, but I must say, this is something of an embarrassment

Re:Ouch

[STrinity]

Wasn't Wolfram's New Kind of Science based on the idea that we don't need no steenkin' peer review?

Is not universal?

[MarsDefenseMinister]

What does that mean? Does this mean that it hasn't been proven to be universal (which is the case if there was just a bug in the proof) or is there another proof that shows the machine is not universal?

kdawson, not proven to be universal and proven to be not universal are two different things.

Re:Is not universal?

[aminorex]

It was proven to be universal, when combined with an automaton that constructs a suitable infinite initial condition.

Professor Pratt, whose contributions to computability, type and category theory are quite substantial and much to be admired, has, yet again, gone off half-cocked, and exposed his attention-seeking immaturity.

Bad Headline

[EvanED]

Wolfram's 2,3 Turing Machine Not Universal

That's not, from my reading, what is true. What is true is that the proof is wrong, which means that it may not be universal, but reverts back to the unknown state.

Re:Bad Headline

[Nimey]

But the correct headline isn't sensationalistic enough.

I don't know if this is the submitter's headline, but furrfu, that's something that wossname, the editor, should catch.

"from the whoa-not-so-fast-there-big-fella dept"

[ZorbaTHut]

Yeah, speaking of that . . .

"Wolfram's 2,3 Turing Machine Not Universal". What? Where'd you get that? This issue doesn't prove anything of the sort - it merely shows that this proof is invalid. It may be universal, it may not, but we still don't know.

So, ironically - whoa, not so fast there big editor.

Bad romantic consequence

[Hao Wu]

I hope that this young man's girlfriend stands by him. So many women would be driven away from an otherwise suitable boyfriend who is skilled at the maths.

Re:Bad romantic consequence

[Torvaun]

Then he'd be following rather closely in Turing's footsteps, wouldn't he? Now that it has been determined that "fags" have you beat in every walk of life, don't you think this is the time for you to stop using that derogatory term?

Or, the young man is a cigarette, in which case I withdraw my objection.

Re:Bad romantic consequence

[fizzding]

If by cigarette, you mean i could smoke him... I never inhaled.

Re:Bad romantic consequence

[Garridan]

Now that it has been determined that "fags" have you beat in every walk of life, don't you think this is the time for you to stop using that derogatory term? Perhaps he's a nondeterministic fag?

Peer Review Rules

[tjstork]

This sort of thing is science when it works at its best. Someone throws something out there, and another scientist checks it, and bam, we learn something.

Re:Peer Review Rules

[Reaperducer]

This sort of thing is science when it works at its best. Someone throws something out there, and another scientist checks it, and bam, we learn something.

Did we learn something? As far as I can tell we're back where we started.

Re:Peer Review Rules

[Anonymous Coward]

We learned that the proof was mistaken. That's how we advance you know, can't hit homerun every time. Even then, we need to check and be able to tell if it cleared the fence or not.

Re:Peer Review Rules

[Wonko the Sane]

We learned one way that doesn't work to prove the hypothesis. Sometimes you have to take what you can get with science.

Re:Peer Review Rules

[ispeters]

Did we learn something? As far as I can tell we're back where we started.

Well, to paraphrase someone famous (perhaps Edison?), we've learned another way that doesn't work. It sounds like the author of the proof has used a faulty syllogism. Perhaps the syllogism can be patched up such that the rest of the proof plus the patched syllogism equals a correct proof.

Ian

Re:Peer Review Rules

[JanneM]

Someone throws something out there, and another scientist checks it, and bam, we learn something. Yep. We learn that "never hold the press conference until after peer review and acceptance of publication".

Re:Peer Review Rules

[tjstork]

Yep. We learn that "never hold the press conference until after peer review and acceptance of publication".

Well, in all likelihood, we really didn't learn -that-. :-)

Every now and then I take a crack at P=NP, and sometimes, I feel like I've really got a good proof - a program idea, that, when implemented, could FACTOR fairly quickly. I'll be practicing my "move over Al Gore, here's what the Nobel Prize is really about" speech as I'm typing my breakthrough in, and there will be some implementation detail that, is just a detail, except that it blows my whole vision and I'm back to square one. And the thing is, when that happens, I never felt like I've wasted my time, because, even though the thing I made did not accomplish its goal, I still made something that satisfied a curiosity, and was able to see the outcome, and learn something, and in a space that I know that not a lot of people are in. It's not like fixing a database bug, that a million other programmers have fixed... it's a different land, about the roots of things, and that's really, very interesting in and of itself.

Re:Peer Review Rules

[maxume]

An optimist would say that this sort of thing is science when it is working fairly well, it would be sort of disappointing to find out that it wasn't ever going to get any better.

Re:Peer Review Rules

[phiwum]

Well, to paraphrase someone famous (perhaps Edison?), we've learned another way that doesn't work. That's hardly the normal effect of peer review. Normally, mistaken approaches are not made public. Rather, they are known only to the author and the reviewer who rejects the submission (even more commonly, to the author alone).

Mathematicians don't tend to share failed approaches too much. They're not usually publishable. Which may be a darn shame, though I must confess I can't imagine wading through pages and pages of failed approaches to be sure I don't duplicate a previous error.

Re:Peer Review Rules

[martin-boundary]

Quite. Failed approaches are a dime a dozen. There's no value in 99% of failed approaches to solving a mathematical problem, because those failures are due to eitherpersonal misconceptions or failure of rigor. If you pick an independent expert, then that expert won't have the same misconceptions (he'll have others) and won't make the same mistakes of calculation (but might make others), so he'll detect those kinds of errors.

The _useful_ failures are the ones which at first pass the peer review process, and are found to be flawed years later. _Those_ are failures worth learning from, because they represent the kind of errors and misconceptions that most people in the field would make routinely, as evidenced by the fact that several independent experts did not catch the mistake during review.

Re:Peer Review Rules

[stranger_to_himself]

This sort of thing is science when it works at its best. Someone throws something out there, and another scientist checks it, and bam, we learn something.

I can't help thinking that we should wait for the authors response to the reviewer before we start judging the original work. Maybe the reviewer has a point, but maybe he doesn't.

Re:Peer Review Rules

[rbarreira]

Every now and then I take a crack at P=NP, and sometimes, I feel like I've really got a good proof - a program idea, that, when implemented, could FACTOR fairly quickly.

Do you mean factor numbers? Even though it would be impressive to have an algorithm which factors numbers quickly, it wouldn't prove anything about the P=NP? problem. Factoring numbers is not known to be an NP-complete problem, so solving it in polynomial time doesn't automatically imply that P=NP.

Re:Peer Review Rules

[darkstar949]

Proving that a known NP complete problem has an algorithm that runs and polynomial time will likely be one of the cornerstones used to create a P = NP proof. Without having an existing algorithm that runs in polynomial time we are stuck with not knowing what route to take to find the proof, if it exists.

Re:Peer Review Rules

[hansraj]

"cornerstone used to create a proof of P=NP".. errm, what?

The very fact that a polynomial algorithm for some NP-complete problem exists *will prove* P=NP. No extra nuts and bolts would be needed.

Re:Peer Review Rules

[slyborg]

NOW he feels like he's been completely wasting his time. Thanks so much.

Re:Peer Review Rules

[tjstork]

Factoring numbers is not known to be an NP-complete problem, so solving it in polynomial time doesn't automatically imply that P=NP

I thought FACTOR was NP-complete... if not, I think you could probably show it to be at least NP-complete by taking the selection of prime numbers as a sort of a napsack problem against a set of "special numbers" or, numbers that one could generate primes with.

Indeed, the one insight that I tried out but failed at was trying to see if I could arrive at what those special numbers were by recursively defining every integer as the addition of two fractions just to see if I could tease out some relationship. What I got was a remarkably inefficient way to create prime numbers.

I just do this for a hobby. I wonder if the problem is, really, that actually generating a prime number is NP-Complete?

Re:Peer Review Rules

[rbarreira]

How can generating a prime number be NP-complete? Do you mean testing if a number is prime or not? That problem is in P:

http://en.wikipedia.org/wiki/AKS_primality_test

Regarding whether FACTOR is NP-complete or not, most computer scientists don't think so.

Re:Peer Review Rules

[darkstar949]

Actually, a polynomial algorithm for an NP-complete problem will not prove that P=NP for all cases in and of itself - the algorithm might just prove it for that family of problems, or the existence might prove that the problem was not in fact NP complete.

Re:Peer Review Rules

[rbarreira]

The definition of NP-complete does not allow for what you just said. A polynomial time algorithm for any NP-complete problem will allow you to solve all NP-complete problems in polynomial time, since you can convert them to each other in polynomial time.

Re:Peer Review Rules

[darkstar949]

That is based upon our current understanding of NP-complete problems we are still operating under the assumption that all NP-complete problems are fundamentally the same where as we may find that a set problem such as the knapsack is not in the same class as the traveling salesman problem.

Think of it this way, to a large extent most computer scientists think that P != NP because a solution hasn't been found yet; however, prior to quick sort, computer scientists thought that O(n^2) was the fastest you could sort because the problem hadn't been understood properly yet.

Re:Peer Review Rules

[rbarreira]

There's a very big difference between the two things you just attempted to compare. While computer scientists may have "thought" that O(n^2) was the fastest complexity for sorting, they hadn't proven so. On the other hand, it is perfectly proven that all NP-complete problems can be converted to each other. The proofs are not complicated and they're perfectly agreed on.

Re:Peer Review Rules

[tjstork]

NOW he feels like he's been completely wasting his time. Thanks so much.

LOL. If you are not afraid to be wrong, then learning is never a waste of time.

Re:Peer Review Rules

[fishbowl]

>[W]e may find that a set problem such as the knapsack is not in the same class as the traveling salesman problem.

That result would make you no less famous than proving P=NP or finding a polynomial-time algorithm for an NP-complete problem.
Good luck with that.

Re:Peer Review Rules

[armb]

If one NP-complete problem can be solved in P, they all can, by definition .

Re:Peer Review Rules

[hansraj]

A problem L is NP-hard if any polynomial algorithm for L can be used to solve all problems in *NP* with only a polynomial slowdown. That is the definition of NP-hard. NP-complete problems are NP-hard and have extra property that they are in NP as well.

So, solving any NP-hard (and hence any NP-complete problem) in polynomial time is as good as solving *all* problems in NP in polynomial time. P is just the class of problems solvable in polynomial time.

Hence, polynomial algorithm for *any* NP-complete problem => (P=NP)

Re:Peer Review Rules

[cicadia]

Aww, we should have waited for him to discover that there's not even a Nobel Prize for mathematics :)

Re:Peer Review Rules

[HuguesT]

No, our understanding of NP-complete problem is that they are indeed all fundamentally the same. Knapsack and TSP are the same problem, as one can convert any knapsack into a TSP in polynomial time, and vice-versa. As a result, being able to solve any knapsack in polynomial time would ensure one would also be able to solve TSP in polynomial time.

Re:Peer Review Rules

[tjstork]

Regarding whether FACTOR is NP-complete or not, most computer scientists don't think so.

Is there a proof though? I'm hardly a computer scientist, and honestly, I'm not terribly smart, but I think FACTOR really is NP-complete.

Re:Peer Review Rules

[rbarreira]

There's no proof either way. It could or not be NP-complete. From wikipedia:

It is not known exactly which complexity classes contain the decision version of the integer factorization problem. It is known to be in both NP and co-NP. This is because both YES and NO answers can be trivially verified given the prime factors (we can verify their primality using the AKS primality test, and that their product is N by multiplication). It is known to be in BQP because of Shor's algorithm. It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find classical polynomial-time algorithms for it and failed, and therefore it is widely suspected to be outside P.

Re:Peer Review Rules

[bzipitidoo]

It is a shame. Thinking is not vulgar.

Where are my meds?

[synthespian]

Jesus Christ, is Wolfram out of Lithium again?

Re:Where are my meds?

[Megane]

Jesus Christ, is Wolfram out of Lithium again?

I think he can find some here.

Re:Where are my meds?

[CompMD]

"Lithium is no longer available on credit"

Re:Where are my meds?

[synthespian]

Can we simulate this with cellular automata?

Re:Where are my meds?

[maxwell demon]

Can we simulate this with cellular automata? Only if they use lithium cells.

Re:duh

[schon]

the universality of Turing machines is... gosh, what the heck does this mean? It means you need to study more for your CS exams.

part of Wolfram's reply cracks me up

[Danny Rathjens]

I don't think that the details of which particular Turing machine is or is not universal are all that significant. http://cs.nyu.edu/pipermail/fom/2007-October/012149.html

I must admit that NKS is a bit over my head at the moment, though. So I could be reading something into it not meant. ;)

Proven?

[pete-classic]

Shouldn't the headline be "Wolfram's 2,3 Turing Machine Not Proven Universal"?

Was this proof the last chance to prove . . . whatever this thing is? Or has a specific attempt merely failed? (According to some email.)

-Peter

Re:Proven?

[Anonymous Coward]

Apparently some Slashdot editors have still to defeat the gargantuan misteries of propositional calculus...

Re:Proven?

[EvanED]

Apparently some Slashdot editors have still to defeat the gargantuan misteries of propositional calculus...

Or, you know, English.

Re:Proven?

[pete-classic]

Awesome.

-Peter

Re:Proven?

[orangesquid]

Yeah... seriously :-/ 8th-grade geometry, anyone? Propositional calculus is something you get in college studying metaphysics, but basic logic is usually taught in high school.

For clarification (we're pretending #1 is true, even though we now know it to be false):
(1) We have a correct proof, so the 2,3 machine is universal
(2) [Inverse] We do not have a correct proof, so the 2,3 machine is not universal (This DOES NOT follow from #1)
(3) [Converse] The 2,3 machine is universal, so we have a correct proof. (This DOES NOT follow from #1)
(4) [Contrapositive] The 2,3 machine is not universal, so we do not have a correct proof. (This DOES follow from #1).
And in prop logic, something is possibly false if it isn't necessarily true (X is possible == Not X is Not Necessary; this is the definition)
(5) We have a correct proof, so the 2,3 machine is necessarily universal
(6) We don't have a correct proof, so the 2,3 machine is possibly not universal
We can pretend {1,2,3,4} is equivalent to {5,6} here. (David Lewis would shoot me.)

Re:Proven?

[orangesquid]

Oops... {1,4}, I mean. .. and I even used the preview button .....

Fool me Once...

[AttillaTheNun]

Don't tell me they fell for the old 2=1 trick!
http://www.youtube.com/watch?v=RkSow7FtWmA/

Ah academics...

[SilverJets]

I love the arrogance.

Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?

Re:Ah academics...

[opypod]

this is how it's supposed to be. someone "has" to be the expert and it's probably an academic. although stephen wolfram was once an academic, he is no longer. he hasn't published a "real" peer reviewed paper in years. in fact, he has no business claiming to do science, "new" or otherwise. wolfram is a software company, and stephen wolfram is a business man and charlatan scientist. by trying to pretend otherwise, he has gotten what he deserved: public humiliation. way to go! p.s. v6.0 mathematica is a bloated sac! thanx for making it worse. btw/ i'm an arrogant academic.

Re:Ah academics...

[mrpeebles]

I agree he could have been more diplomatic. Still, it is pretty crappy to let a student (an undergrad if I recall) publish a now embarrassing proof with an error that is apparently pretty obvious to an expert. That is sort of how I read this comment.

Re:Ah academics...

[Chase Husky]

Even peers or professors from the Ivies, or major institutions, agree that a majority of people that are at, or have graduated from, Stanford are assholes.

Title Proven To Be Misleading

[yerdaddie]

The Wolfram's 2,3 Turing Machine proof of universality was found to be flawed. This does *not mean* the 2,3 Turing Machine isn't universal. It just means it has not been proven to be universal. That would require another proof. Subtle distinction, I know; but in any case, the title of this article is fallacious.

Re:Title Proven To Be Misleading

[gonzoxl5]

I didhn't think fallacio was allowed on this site ?

That opens another question

[Opportunist]

That proof ain't a simple logic tree that you can follow in your head and nod. I for sure could not have found the error (though my degree isn't in math, and it's been a while...). Sure, those people are closer to the core of top level math, but still... I mean, don't you make mistakes when you program? Despite being a top level coder?

The question that keeps nagging me now, though, is, whether this is the only incident. Or rather, what if there're more "proofs" out there that are actually none? The way research works, we rely on proven concepts to build our own research on top of it. What if our foundations are shaky? Does anyone actually test old theorems that were proven (or falsified)?

Re:That opens another question

[samweber]

So, an undergrad makes a relatively silly mistake in a proof, and the mistake is found before his paper even gets through the referee process. What's the big deal that keeps nagging at you?

Yes, people check proofs. The name "Vaughan Pratt" comes to mind as an example.

Mathematicians are extremely dedicated, because there is incredible competition to get a Ph.D. in mathematics, and in order to get a job doing pure math one practically has to wait for someone to die. It is something one only does if one is both extremely talented and in love with the subject. So, any new result in a field is going to be looked at carefully -- for fun if nothing else.

Re:That opens another question

[Anonymous Coward]

The question that keeps nagging me now, though, is, whether this is the only incident. Or rather, what if there're more "proofs" out there that are actually none? The way research works, we rely on proven concepts to build our own research on top of it. What if our foundations are shaky? Does anyone actually test old theorems that were proven (or falsified)?

You're making a mountain out of a mole hill. In this case a student published a proof in a journal of non-peer reviewed work. When it was peer reviewed an error was found. The fact that one young mathematician made an error should hardly cause you to lose faith in the validity of every other theorem proven to date (especially the ones that other scientists actually looked at).

Re:That opens another question

[alienw]

The question that keeps nagging me now, though, is, whether this is the only incident. Or rather, what if there're more "proofs" out there that are actually none? The way research works, we rely on proven concepts to build our own research on top of it. What if our foundations are shaky? Does anyone actually test old theorems that were proven (or falsified)?

There is no point in doing that. If you can build a large self-consistent mathematical structure on a basis of some results, especially a structure that is useful, it is a positive result. If a foundational theorem was wrong, you would not have been able to build anything on top of it -- soon you would run into an inconsistency, an absurdity, and you would see that something is wrong. If an assumption does not result in an absurdity, then it's perfectly valid to build mathematical structures on top of it; in fact, that is how many areas of mathematics got created. People either found that a certain axiom could be removed, or that additional assumptions opened up interesting and nontrivial possibilities.

Re:That opens another question

[wmspringer]

I believe there was an attempt a number of years ago to go back to the basic axioms and reprove everything, but I don't remember the details.

Re:That opens another question

[Architect_sasyr]

There's been a lot of comments on whether it is a proof or not and how research works and so forth, but I'd like to make one point: If I have a "proof" that later proves to be false, but with this "proof" I develop the cure to cancer, does it really matter? Some of the greatest "features" I have seen in programs are items that the programmer thinks is a bug in the code, written by some of the best programmers I know. So what if the foundations were shaky? Nitro-glycerine was discovered by accident...

Re:That opens another question

[Mode_Locrian]

Yeah, this sort of thing has definitely happened before. When Frege published his (groundbreaking) account of set theory, everyone thought it was the greatest thing since sliced bread--until Russell showed that it entailed a fatal paradox (namely, that there is a set, call it R, that contains all and only those sets that don't contain themselves. Hence, R contains itself if and only if R doesn't contain itself). Similarly, Kurt Goedel proved in 1931 that the Russell/Whitehead language for first-order logic (and, indeed, any language complex enough to express simple arithmetic) is incomplete if consistent--despite the completeness proofs which were already published. Plenty of other cases abound. By (simple) induction on the history of mathematics, it appears probable that some results which we currently take as proved are actually false (or unproven, at least). So where does this leave us? Must we embark on a Cartesian quest for Absolute Certainty? I think that's probably not the best way to proceed. I like Otto Nuerath's analogy better: we are (epistemically) like people afloat on a raft at sea. As we discover leaks in the raft, we fix them and then move on; it's not as if it would be wise, upon discovering a leak, to destroy the entire raft and start over with a better engineering design (i.e. begin with something like Cartesian foundations).

Re:That opens another question

[Mode_Locrian]

Are you thinking of the Hilbert Program http://plato.stanford.edu/entries/hilbert-program/? A really interesting idea, but it ultimately failed due primarily to Goedel's incompleteness proof (though in a talk I recently heard, Saul Kripke shows that Goedel's proof wasn't necessary to bring about its demise--the program fails due to internal inconsistency).

Re:That opens another question

[Alzheimers]

Or, you just add another dimension to your theory of the universe, and keep on going...

No, just not proven

[billstewart]

As others have pointed out, no, it doesn't mean anybody's proven that it's not universal, it just means that this alleged proof of universality was incorrect.

Re:No, just not proven

[Larry Lightbulb]

I think the OP is pointing out that the headline of "Wolfram's 2,3 Turing Machine Not Universal" should be something like "Wolfram's 2,3 Turing Machine Not PROVEN TO BE Universal" and that it's a comment about the poor editing of this story, rather than expressing confusion about the content.

Can I get a refund

[stinkfish]

for the Wolfram's 2,3 Turing Machine I bought from amazon?

Re:Can I get a refund

[MillionthMonkey]

What a pity you can't rely on your 2,3 machine to compute whether Amazon will refund your money in a finite time.

Re:Can I get a refund

[rubycodez]

only if the infinite tape is mostly unused

Re:Can I get a refund

[Anonymous Coward]

Just cut out the used part, and tape the two ends together. No one will ever know the difference.

Back to the drawing board

[tepples]

Does this mean that it hasn't been proven to be universal (which is the case if there was just a bug in the proof) It appears to mean the proof has a defect in the same way that message passing in Windows has a defect. As far as I can tell based on the article, Vaughan Pratt alleges that so much of the proof relies on the defect that the proof would need a complete rewrite.

Re:duh

[ispeters]

You sound like a troll since you're so belligerent, but, in case anyone else here is legitimately wondering what it means for a Turing machine to be universal, I'll try to answer.

Basically, a Turing Machine is an abstract "computer"--it's a tape (a skinny piece of paper) that has a start but no end (it's infinitely long, but it has a start), and a read/write head that can zip up and down the tape writing, reading, and erasing symbols on the tape. The Church-Turing Thesis postulates that a computable algorithm is any algorithm that can be computed in a finite number of steps by a Turing Machine. There are some things that look like algorithms and seem like they should be computable but are in fact impossible. The classic example is the Halting Problem.

Anyway, a regular Turing Machine only computes one function--it's a single-purpose machine. A Universal Turing Machine is a Turing Machine that can simulate any other Turing Machine by interpreting a codified description of the other machine. Since every computable function is isomorphic to some Turing Machine and every Turing Machine can be simulated by a Universal Turing Machine, every computable function can be computed by a Universal Turing Machine. The computer you're using to read this is an approximation to a Universal Turing Machine (the RAM would have to be infinite in size to be a proper Turing Machine), and the codified descriptions that it interprets are the binary executables that you run on it.

Hope that helps,

Ian

Pay back?

[PHAEDRU5]

Will Smith have to return the $25k?

Re:Pay back?

[ruinous]

What does Will Smith have to do with this?!

Wolfram chimes in

[snark23]

Wolfram's lengthy response:

http://cs.nyu.edu/pipermail/fom/2007-October/012149.html

Re:Wolfram chimes in

[Plutonite]

So much talk, so little value. Holy shit, I miss the days of Feynman and Einstein and Max Born. What is happening to the world? Must everyone defend to the death every silly mistake they make? If you're wrong, you're wrong; we don't want to hear about your philosophy in life and your contributions to mankind and your plans for the future, just apologize and get on with science. Jeezus.

Re:Wolfram chimes in

[Vickor]

Maybe I didn't read it well enough, but that link isn't a response to the post by Pratt.

Re:Wolfram chimes in

[snark23]

It doesn't directly address Pratt's point, but it addresses some of the things raised in the discussion that followed Pratt's post regarding universality.

Turing machine and Linux?

[Soleen]

Does it run Linux?
No certain anwer yet again.

I rate this proof

[MillionthMonkey]

(Score: 2,3 Possibly Informative)

Re:I rate this proof

[Kelz]

Wouldn't that be (Score: 2,3 Possibly Insightful)?

Re:I rate this proof

[Alsee]

(Score: 2,3 Possibly Universal)

-

Re:I rate this proof

[onemorechip]

(Score: 1,2 Overrated)

Until its badly reported

[EmbeddedJanitor]

If it aint universal it aint a Turing machine

Re:Until its badly reported

[Michael Woodhams]

Sorry, but that is just flat wrong.

A universal Turing machine is one which can simulate any other Turing machine. There are very many non-universal Turing machines, such as one which just writes an infinite sequence of '1's.

Alright, Einsteins....

[Urusai]

...so there is an assertion that the putative proof is flawed. How many of you read the proof and can verify that the assertion is correct? Accusing the proof reviewers of laxity seems kind of hypocritical.

Re:Alright, Einsteins....

[SimonBelmont]

Um, no, the problem is there were no proof reviewers. This was just Wolfram being overly eager for a chance to once again assert his superiority over the scientific community.

"We're excited to announce that the $25,000 Wolfram 2,3 Turing Machine Research Prize has been won." http://cs.nyu.edu/pipermail/fom/2007-October/012120.html

"As far as I know, no member of the committee has passed on the validity of this 40 page proof. The determination that Smith's proof is correct seems to have been made entirely by the Wolfram organization. My understanding is that the I/O involves complex encodings." http://cs.nyu.edu/pipermail/fom/2007-October/012132.html

Elmentary Mistake in Title

[Cyberllama]

This doesn't mean it's not universal, just that it's not PROVEN that it is. Not at all the same thing.

Re:Elmentary Mistake in Title

[aminorex]

Your claim that it is not proven is an unproven (and controversial) claim.

Subject is wrong

[thomasoa]

The subject of this article is wrong - we do not know that Wolfram's 2,3 Turing Machine is not universal. We only know (assuming the proof really is in error) that there is no proof either way as to whether it is universal.

The prize stands -

[Anonymous Coward]

he was just using a new kind of proof.

prize money

[drDugan]

I hope he's already cashed the check.

Wow...

[graviplana]

Jeez, Can someone please give me the short version explanation about why everyone is bagging on Wolfram?

Re:Wow...

[jpop32]

Jeez, Can someone please give me the short version explanation about why everyone is bagging on Wolfram?

Well, the very short version is that he is not a very nice person. And, basically, he said 'fuck you' to the traditional scientific community and went his separate way, turning from a prodigy to an outlaw. Which the traditional scientific community didn't appreciate much. And now they are, more or less, openly out to get him.

Which is, IMHO, unfortunate, because his scientific ideas should be judged on their merits alone.

Vaughn Pratt is confused

[evgalois]

No, Vaughn Pratt is confused. There is a post from on the FOM mailing list that explains the confusion. There are subtle issues concerning the nature of computational universality in the presence of infinite initial conditions. Vaughn Pratt is probably remembering work from the 1950s on computational universality, which does not address these issues. There are different definitions that could be given for computational universality with infinite initial conditions. Alex Smith's proof was verified with a particular, natural, definition that was chosen for the prize. So all is well. The 2,3 Turing machine's universality has not been toppled with one email and the personal opinion of Vaughn Pratt. What has happened, though, is that questions that have not been discussed since the 1950s are (this week) back in vogue again.

Re:Vaughn Pratt is confused

[Ed Pegg]

I'm posting from Wolfram Research. Basically, a message from Vaughan Pratt was posted to the correct spot, the FOM list. Dr. Pratt likely didn't expect his message to get a late night SlashDot level exposure. A response to his message has already been sent to the FOM list, but it is a moderated list, and the response is not visible yet. Here is a copy of the FOM posting from Todd Rowland, from the Wolfram prize committee. http://forum.wolframscience.com/showthread.php?s=&threadid=1472 This is how math is done ... trying to poke holes in proofs.

Re:Vaughn Pratt is confused

[Anonymous Coward]

Since you are posting from the heart of the Wolfram Hype Machine (TM), perhaps you could comment on why the prize was announced by Wolfram Himself as being successfully awarded, when Martin Davis on the FOM list states that the committee members were not polled.

This appears to be a flagrant violation of the rules for the prize, which state that "For the purposes of this prize, the treatment of universality in any particular submission must be considered acceptable by the Prize Committee."

To make my question crystal clear: how is it possible that the committee deemed the proof (or its treatment of universality) acceptable when at least some of them were not polled as to whether they thought the proof was acceptable?

p.s. Please don't appeal to a "New Kind of Logic" or a "New Kind of English" in your answer.

Re:Vaughn Pratt is confused

[jeremym42]

"What has happened, though, is that questions that have not been discussed since the 1950s are (this week) back in vogue again." Key point. This discussion is direct evidence. The majority of the replies to this thread are cheap blows at Stephen Wolfram, and jealous comments about Alex Smith. If you want to discuss the science behind Wolfram's work, then do that. Obviously Wolfram is searching for something that very few understand at all. All of this childish sarcasm shows how Wolfram's concepts in "A New Kind of Science" are less understood then they should be for proper peer review. Stop trying to play if you don't know the rules! It's like discussing free trade with a sociologist and an economist from the University of Chicago - they're not on the same page. Don't get me wrong - the main point is - you're not upsetting Wolfram, you're only inspiring him.

Re:Vaughn Pratt is confused

[ortholattice]

From the post you mention:

Smith's use of non-repetitive infinite initial conditions is controversial, but is a natural extension of current definitions which allow infinite repetitive initial conditions. We hope that the ensuing discussion will enrich debate in the scientific community concerning the nature of computational universality.

Whenever a generalization of the definition of a universal Turing machine is put forward, that the status of some machines will necessarily change from 'non-universal' to 'universal'. It is a challenge to explicitly construct a machine with initial conditions similar in spirit to Smith's, that is obviously too simple to be considered universal, and which is performing a universal computation with those infinite initial conditions.

"The status of some machines will necessarily change from 'non-universal' to 'universal'"??? This sounds like a cop-out to justify the error in the proof: re-define the problem so the proof fits it.

Let's generalize the definition of FLT (Fermat's Last Theorem) to include n=2. It seems to me this is a "natural extension" of its current definition. Guess what, I have a truly marvelous proof that FLT in a generalized sense is false, which the margin of this post is not too narrow to contain: 3^2+4^2=5^2.

Seriously, once you have fixed the statement of a problem in mathematics, there is no "controversy" as to whether it is true, false, or undecidable, and a correct proof will show which one of these three is be the case. Someone else can't come along and show that another of these three is the case, unless one of the proofs is flawed (or unless the foundations of math are inconsistent, which would be a major discovery in itself). In this case it appears that Smith's proof is flawed and simply does not prove the stated problem. It sounds like Wolfram Research is twisting the definition of the problem to save face, rather than just admitting the proof is flawed and moving on.

Earlier in that post,

Alex Smith did not only show that the encoding of the initial condition is non-universal. He showed that the encoding is very computationally weak and then concludes that the Turing machine is universal in a generalized sense.

Well, allow me to generalize even more. I'll define anything that can perform the computing done by an AND gate as universal in a super-generalized sense. I conclude that a Turing machine is universal in a super-generalized sense. Let me sell you my line of AND gate computers. If you complain that they can't do much, I'll merely point to my proof that they are universal in a super-generalized sense, just like Turing machines.

Re:Vaughn Pratt is confused

[evgalois]

Here is the explanation about the suposed "flaw", which of course it is not: http://forum.wolframscience.com/showthread.php?s=&threadid=1472 And my comments on the guy that thinks that the universality definition was changed for the prize benefit (I am surprised about how many people write about this without knowing a bit of the subject and trying to sound technical talking about "AND gates" completely nonsense): Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines, which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done. We particularly hope that his methods can be extended to other similar proofs.

Re:Vaughn Pratt is confused

[Cheesey]

This has been posted elsewhere in the discussion, but you might like to read what academics think of Wolfram's magnum opus: here. It seems that people who do understand it think that it is not particularly original, repeating many known results from previous work (without citations), and also saying things that are actually wrong.

The ideas about the Universe as a giant cellular automaton are particularly bizarre, I think, but then I have always had trouble with seeing myself as being equivalent to a computer program. It's all reminiscent of the Hitch-hiker's Guide, actually, since Wolfram is effectively saying that you can extrapolate all possible states of the Universe from a piece of fairy cake, then build an artificial Universe that is equivalent to the real one. Then, presumably, you can do any scientific research from the comfort of your office, and still be able to go to parties in the evening. Sounds great, if unlikely.

Re:Vaughn Pratt is confused

[SpinyNorman]

From the Wolfram Research response, Pratt is right on the money. The 2,3 machine is not universal in the sense that is conventionally accepted. Wolfram have just decided to use a much relaxed definition of universality (infinite initial conditions) that the 2,3 machine does meet. Less interesting than the headline claim.

Quoting from the response:

When Minsky posed the question of finding the smallest universal Turing machines in 1967 [1], he restricted the problem to Turing machines with finite initial conditions. Indeed, arbitrary infinite (but non-computable) initial conditions can allow a machine to solve the halting problem and perform other miraculous computations that are seemingly impossible in our physical universe. Clearly, Minsky was justified in forbidding arbitrary infinite initial conditions.

Their defense of the 2,3 machine is that the particular type of infinite initial conditions it requires prevents it from being trivial, but this doesn't change the fact that it doesn't meet Minsky's definition, and it's certainly not going to be the basis for any molecular computers except those running in a different universe with an infinite number of molecules.

Re:Vaughn Pratt is confused

[ortholattice]

Here is the explanation about the suposed "flaw", which of course it is not:

"Of course"? I'll take Pratt's word over yours.

http://forum.wolframscience.com/showthread.php?s=&threadid=1472 And my comments on the guy that thinks that the universality definition was changed for the prize benefit (I am surprised about how many people write about this without knowing a bit of the subject and trying to sound technical talking about "AND gates" completely nonsense):

Irrelevant ad hominem. Yes, my example is a little silly and exaggerated, but the point stands. Any machine at all is a "generalization" of a Turing machine. The way the post I responded to was worded almost made it sound like generalization was good thing - "concludes that the Turing machine is universal in a generalized sense" is an obvious, meaningless tautology. Of course it is; it can emulate any other machine, including 2,3. You don't need Smith's proof to "conclude" that as if it were some new discovery.

Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines, which is a generalization of previous definitions.

A Turing machine is a precisely defined and well-studied mathematical object, and this generalization is apparently not equivalent to it in any mathematically acceptable sense.

If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape).

These sound like weasel words to me. "There is no clear definition"? "Others accept"? While I'm not an expert in the field and may not be familiar with all of current literature, I have some background in Turing machines and find it hard to believe that the time-tested and quite clear mathematical definition has been abandoned by any serious researcher. Literature references please.

Re:Vaughn Pratt is confused

[evgalois]

This post is as ridicoulous as many others following this thread. The definition used in the proof has been used in the Small Turing Machine community since many years ago, namely Watanabe, Rogozhin, and many others. It wasn't an invention of Wolfram, Alex Smith or the reviewers but a contribution of Alex Smith to the debate of universality since he is not using periodic backgrounds but non-periodic simple ones. Furthermore, it is much more likely to find tape backgrounds with some pattern than "blank" tapes... And if you prove that the background is computationally simple so you don't need another universal machine then it fulfills the basic requirements of universality. Don't confuse yourselves with "infinite initial conditions" just because there is an infinite pattern on the tape. It is exactly the same than the "infinite tape filled with blanks". You don't need an infinite number of molecules to build this machine, you just need 6 elements (2 states x 3 colors) and you will find that your machine can behave universal because it is not going to find blank tapes around but many patterns interacting with it. Don't be fool an inform yourself or think a little bit.

Re:Vaughn Pratt is confused

[evgalois]

Well, that's a good start: you accepting you are not an expert in the field but pretending to judge something that of course experts reviewed. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to critic others. The definition of universality has been modify several times, the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Smith contribution is a generalization of the same sort. If you want some references feel free to check these and then reply again: [1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996. [2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer. [3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003. [4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer. [5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, France, September 2007. Springer. [6] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240, November 1996. [7] Shigeru Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, October 1961. [8] Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of Information Processing Society of Japan, 13(9):588-592, 1972. That is why many serious authors as Vaughn Pratt can be confused. Because they are not updated on the subtles of the field. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done.

Re:Vaughn Pratt is confused

[evgalois]

From the FOM list where most of you jumped to conclusions without even waiting to an official answer from Wolfram Research: 1. Concerning the prize committee, we did not expect them to go through the details of the proof but to support the reviewers on technical issues related to their fields of expertise. We would have been delighted to have had them spend more time on the proof but that wasn't our expectation. We did talk to people about how to set the prize up. Basically we needed judgement about their areas and we were very careful to cover those that could come up in a universality proof. We are grateful to the committee for covering those areas and we are happy that they were more active than many such committees. In the review process, committee members agreed with the Wolfram Science internal reviewers, while others asked for additional clarifications (such as fulfilling universality basic requirements for non-halting machines). All committee members had Alex Smith's proof in hand for a couple of months. But it was Wolfram staff who did the hard work to achieve a satisfactory level of verification (between revisions and revision requests), and we thought that by waiting any longer we would not have learned more. It helped that a lot of the proof was submitted in the form of programs that could be run and analyzed in a systematic way. Smith's proof is available to everybody, anyone can point out anything, and it is nice to get the sense that there are people out there who would be interested in verifying proofs. This is great news, and if we do other prizes we would definitely like to take advantage of that. We would be also delighted to hear opinions on how to set up next prizes. 2. Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines (see detailed references below), which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. One could fairly argue that two non-universal coupled automata can reach universality, but it would require the couple to interact at every step, as in Margenstern's nice example [1], but that's very different from a non-universal second automaton intervening only once at the first step. We are glad that this is making a contribution to the discussion on universality. We expect that others will further clarify what Alex Smith has done. We particularly hope that his methods can be extended to other similar proofs. Accepting that you are not experts in the field but pretending to judge something that of course experts reviewed is a good start. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to criticise others. The definition of universality has been modify several times (if one can say so, since there is no original or first accepted definition), the first to make a generalization exactly as the used by Alex Smith was Watanabe as early as in the 60's. Alex Sm

Re:Vaughn Pratt is confused

[polymorpheus]

So does that mean the proof is valid for some suitable definition of universal and that the prize will be awarded?

Re:Vaughn Pratt is confused

[greginnj]

Well, that's a good start: you accepting you are not an expert in the field but pretending to judge something that of course experts reviewed. It is nice that people like you think on this problem and possible flaws, though. Of course nobody is changing the well stablished definition of a Turing machine. But it is accepted even by the experts that there is no clear definition on universality. You should follow all the FOM posts and not only those that you think are better to critic others.[...]

Hmm, let's see:

1. Brand-new user posting only to this thread? Check.

2. Username derived from the name of a famous mathematician? check.

3. Snarky "no one outside our company understands how revolutionary all this is" attitude? Check.

Yep, you're a perfect Wolfram employee -- you've got the self-aggrandizing persecution complex down pat. Make sure you don't say anything that hasn't been pre-approved by the Generalissimo, though, so you don't get sued. Only one guy working there gets to name a whole new branch of science after himself, you know.

Re:Vaughn Pratt is confused

[maxwell demon]

It's all reminiscent of the Hitch-hiker's Guide, actually, since Wolfram is effectively saying that you can extrapolate all possible states of the Universe from a piece of fairy cake, then build an artificial Universe that is equivalent to the real one. Then, presumably, you can do any scientific research from the comfort of your office, and still be able to go to parties in the evening. Sounds great, if unlikely.

You mean, Wolfram is currently working on the ultimate torture device?

Wrong, that is NOT Wolfram's response

[Weyoun]

Incorrect - that is not Wolfram's response to Pratt's message, it is a response to an earlier message. Compare the dates.

Cut him some slack.

[Dean Hougen]

Hey, even an Einstein divides by zero now and then.

Serious authority

[Emnar]

I don't understand the math behind this argument and counter-argument, but Vaughan Pratt is a CS legend and one of the early cofounders of Sun, to boot. You also might have run across his name in a cite or two in The Art of Computer Programming series by Donald Knuth. And if you don't care who Knuth is, then you probably don't care about this post at all.

I knew Pratt's daughter in college -- nice woman. Wrote her term papers in LaTeX, on a Linux workstation, in 1996 :P

Paper stages

[Goonie]

When you submit a paper for publication in a journal, it gets sent away for peer review. If the peer reviewers like it and say it should be published, there will customarily be a delay between when you're notified and when it is actually published, sometimes a very substantial delay. You can then, generally, put the paper in your CV as "accepted for publication" in whatever journal it is, or, if necessary, cite it as such.

This paper sounds like it had reached the "accepted for publication" stage, which means it had indeed undergone, and passed, peer review. It's a bit embarrassing to have a paper make it through peer review with a serious mistake, caught soon after, but it does happen (if I recall correctly, it happened to Donald Knuth once).

On a slightly related note...

[mdenham]

Am I misinterpreting things when I think that the combination of a universal Turing machine and Gõdel's undecidability theorem ends up proving that for every UTM there exists another Turing Machine (possibly itself, but irrelevant) that can't be simulated on it?

Re:On a slightly related note...

[chgros]

No, not at all, for a Turing machine to be universal means that it can simulate any other Turing machine.
Gödel's incompleteness theorem (although I don't remember it so well) is more akin to the impossibility of the halting problem.

Re:On a slightly related note...

[Workaphobia]

> "that for every UTM there exists another Turing Machine (possibly itself, but irrelevant) that can't be simulated on it?"

No, a universal Turing machine (or "The" Universal Turing Machine) can run all Turing machines including itself. Godel's theorem would have more to do with the fact that the UTM is not a decider, but the problem is still Turing-acceptable ("semi-decidable").

However, we can talk about higher-order Turing machines that make use of oracles to decide otherwise uncomputable problems, and then say that these are above the level of ordinary UTMs, but not above higher level UTMs... This is the basis for talking about Turing degrees - if we're given a means of solving one strange problem, what kinds of other things can we do. These other Turing machines cannot be constructed from the strict formal model, however, as the seven-tuple doesn't allow for the notion of an oracle.

Please correct me if I'm mistaken about this.

The really damning thing from the FOM list...

[Bob Hearn]

... is this:

http://www.wolframscience.com/prizes/tm23/technicaldetails.html

It says there that for the prize, the notion of universality is to be judged
acceptable by the Prize Committee.

I clicked on Prize Committee:

http://www.wolframscience.com/prizes/tm23/committee.html

And found these members:

Lenore Blum
Greg Chaitin
Martin Davis
Ron Graham
Yuri Matiyasevich
Marvin Minsky
Dana Scott
Stephen Wolfram

Since the prize was awarded, what definition of universality was used during
the deliberations?

In particular, Martin Davis, Ron Graham, and Dana Scott are subscribers to
the FOM list. What definition of universality are they using?

Harvey Friedman followed by:

...
But, as I said in an earlier message, although the committee was kept
informed, we were never polled.

Martin

                                                      Martin Davis
                                        Visiting Scholar UC Berkeley
                                            Professor Emeritus, NYU Let's see Wolfram explain that.

In Soviet Russia...

[br4v3_s1r_r0b1n]

...the 2,3 Turing Machine proves that Wolfram is universal! Sometimes I just kill myself...

Re:MOD PARENT DOWN. IRRELEVANT LINK, KARMA WHORE

[snark23]

Wow. You're an angry dude.

I didn't look at the dates. I arrived that post by clicking "next in thread" from Pratt's post, so it seemed to be in chronological order.

You can simulate anything

[Tharkban]

A universal Turing machine can simulate any Turing machine on any input.
The trouble in simulating itself, is that you need to encode the input of the simulated machine.
So to simulate itself running, you need an encoding of itself to take as input.
This is problematic.

math the religion

[slew]

Sadly, it seems to be the case that there is only a small fraction of the math and science worshiper that have fallen from the "purer" faith and dare question the high priestess of truth promulgated by the science and math establishment.

Euler was probably one of the people responsible for some the old theorems that are the foundations of mathematics. Euler had some famous flaws in his early proofs (most notably his polyhedra formula and radical product proofs). These proofs were fortunatly repaired along the way as people discovered them.

Like many religions, math has beatified some of it's saints, and no more famous than Saint Fermat. Now days, the conventional wisdom is that Fermat's famous margin proof was likely to be invalid, but for many years, true believers refused to knock down his alleged proof even as the evidence to the contrary mounted. Sadly as with many artifacts for religion, the elaboration of the proof doesn't exist, we only have the gospals of the proof and the interpreter of the gospal to tell us the story of this feat.

The four-color map theorem was another prophecy that has a storied history. The chancellor of the Dioces of London (mathmetician sir alfred kempe), published a proof the the four-color map theorem that went unchallenged for 11 years when the reformation of Percy Heawood showed the proof to be incorrect. The current standing proof of the four-color map theorem is a computer proof. That fact alone might ring some alarm bells with you.

No doubt that as the understanding of math advances, more proofs will be reconsidered and more often than not open up new avenues for new discoveries. There will still be those of the "pure" faith (the fanbois) that cling to the proclamation of the establishment and say everything is "settled" and attempt to silence the heretics, but the doubters that are testing the old "proofs" may be the ones that actual people praticing "real" faith. Time will tell.

Extended Peer Review

[Per Abrahamsen]

You could argue that scientist reading each others articles and commenting on (and finding fault in) them is also a peer review. Public this time.

Re:Extended Peer Review

[martin-boundary]

True, but don't forget that this "public peer review" occurs conditionally upon the journal's peer review being successful. So the input to the "public peer review" is statistically biased in favour of papers with less trivial faults.

wolfram inc. sinking deeper and deeper

[tlord]

I have read and followed all of the related threads on the FOM mailing list. I am also familiar with how restraint in expression works in academia vs. slashdot. Academic restraint of expression in the emails has led to some confusion on slashdot: Vaughn Pratt's objection is indeed elementary and, if true, unassailable. Vaughn Pratt has pointed out that the proof says, essentially, "the 2 state, 3 color machine in question is universal -- if you add some more states". Is that objection true? The recent responses from Wolfram Inc. have said, "yes, it is." They say so explicitly. Game over. Except wait: Things have now turned obscene: Wolfram Inc. first of all misled this student, badly when they advised him about the paper. Now he has the embarassment of being the victem of a controversy on his record. Wolfram Inc. exploited this student badly. I have yet to see any public statement from Wolfram Inc. about the matter that does not seem to me to be primarily aimed at promoting the "NKS" book. Wolfram the man has, in my opinion, embarassed himself badly. The elementary error is not only in the proof, it is in the rules of the contest. It is not written out in the rules of the contest -- the rules cite certain passages of the book, where the error is offered as fact. The heat-of-the-moment responses from Wolfram Inc. have, clearly to anyone familiar with the dialects and who has read the threads, evaded the issue. In my opinion, they have offered handwaving (and self promotion) of the worst kind. There is, as indirectly pointed out on the FOM mailing list, some chance that the 2-3 machine may yet turn out not only to not be provably universal, but perhaps even to be a clear refutation of the main thesis of NKS (as nearly as said thesis can be generously rendered as a coherent statement, in my opinion). So, it's a freaking mess. In the standards of the academic world, this is a 100-year flood kind of boner of a mistake, to put it mildly. I call upon Wolfram and Wolfram Inc. to own up, make a serious effort to articulate their critic's best arguments in plain language accessible to the slashdot crowd, and then explain how they will proceed justly from there. Otherwise, in my opinion, they will just be furthering their exploitation of others. -t p.s.: my best guess is that the lame responses from Wolfram Inc. are there to buy time -- they want 48-96 hours to rack their brains and rescue the proof. And there's a chance! Not a great chance, but a chance. For example, if it turns out that encoding the student's construction in a meta-circular interpreter (writing a program to cause it to simulate itself) results in an initial config that only needs to initialize a finite amount of the tape -- that would complete the proof. (Doesn't seem likely, from what I understand so far, but that's just my guess.)

Re:wolfram inc. sinking deeper and deeper

[evgalois]

Wolfram exploited this student? This student was free to submit his proof and won 25 K! I would like to be exploited like that... You are wrong, taking the word of a guy as a peer review of a proof, and then come here and talk as if everybody knew about the topic. You are sharks feeding yourselves. That is the obscenity. You talk about "the standards of the academic world". Do you mean that world that produces thousands of papers that nobody reads except the referee? Do you think all papers and proofs are flawless? Wolfram Research is a company that want things to get done, well and fast. It is not a university and you don't have to expect them to behave as if they were. They don't want to be either. It is their prize and their money. Before taking the word of someone sending an email with his personal opinions in the FOM list, go an inform yourself. At least wait for the right to answer before spreading your ignorance worldwide.

Re:wolfram inc. sinking deeper and deeper

[tlord]

Yes, exploited. It's a professional embarrasment at the start of his career. I'm not sure $25K is a fair price.

It's a basic logic problem. The original challenge problem could be restated: "Prove either that there exists a non-universal machine which emulates the 2-3 machine OR that the 2-3 machine can only be emulated by a universal machine." The proof does neither. Wolfram Inc. reps have come back with "Well, perhaps we should change the definition of universality!" Only, they aren't very concrete in offering an alternative with any rigor and the vague suggestions they are making don't add up (e.g., don't answer Vaughn Pratt's counter-example of paired push-down automata).

What the student proved here may turn out to be an interesting and useful result (not the universality of 2-3 but the universality of this interesting combination of machines). Students should be encouraged to work on such problems. Students should be encouraged to write as well as this student is learning to do -- it's a nicely presented paper (trivial formatting bugs aside). But students shouldn't be encouraged to go in those directions on false premises.

At least two interesting questions come from the students work. To Wolfram Inc.'s credit, they are pointing in the general direction of these new questions (even while not yet acknowledging their mistake). The new questions: Do there exist simple machines whose universality is undecidable (and might 2-3 be an example)? If 2-3's universality is either false or undecidable (and especially in the latter case) can we find any useful structure to what combinations of it with other machines clearly are universal?

I'll leave it as an exercise to figure out how raising those questions relate to the "Priciple of Computational Equivalence" in NKS but, meanwhile, leave the student out of it!

We'll see. With an additional step that "finitizes" the student's construction the proof is rescued and raised to the status of an important lemma -- but if that step isn't very quickly forthcoming, the prize -- in no small part an advertising vehicle -- was administered in a pedagogically misleading way.

-t

Yeah, but Wolfram is an asshole

[tjstork]

That's the whole point. I'm not jealous of the guy at all. So what, he learned a bit of math by writing a symbol interpretor and now he thinks he's god's gift to humanity? Big deal... all Mathematica is, at the end of the day, is a big fricking tree transforming engine that is theoretically no more advanced than the lowly XSTL processor.

In my mind, if he wants to be god's gift to humanity, get on with a hard problem and quick dicking around with all this peripheral stuff. Find out if P=NP. Perfect nuclear fusion... or come up with a faster way to do fluid and plasma simulations. It's not like there aren't real problems.

Smarter people have done more, and have been more self effacing, and more humble.

So screw Wolfram, and his stupid Mathematica. It's the patent that protects that product, not his genius, for sure.

Give Wolfram some credit

[Starky]

I have heard time and time again on Slashdot that Wolfram just took other people's work, that he had people working underneath him & that he didn't actually know what he was talking about in his book. This is some corroborating evidence, in my opinion.

Hardly. Wolfram disappeared for a decade to produce A New Kind of Science. Was he picking his toes while his team of crack Mathematica techies were developing the ideas for the book? I find that hard to believe. In fact, the way I heard it, he did all of his own editing on the book, much to the dismay of some who found it in need of editing.

He probably did have staffers assisting in running simulations (and with his bankroll, I would certainly entertain that notion myself), but name me one prominent professor who hasn't stood on the shoulders of graduate students.

Whether you consider him a genius or a crackpot (and he certainly gives reason to entertain both opinions), Wolfram is undoubtedly brilliant and seems to be dedicated to the advancement of mathematical ideas that he considers to be important. It hardly seems that a lack of academic integrity would be consistent with his actions to date.

Whether history will ultimately judge him a genius or a crackpot, I would guess that he has done more to advance mathematics than all the posters to this article combined, myself included. So give the man some credit.

Re:duh

[Workaphobia]

That was a well put and concise explanation.

Now, my take on this whole thing was that the question is: whether there exists a way to encode* any Turing machine and string as input to this particular machine, such that it accepts if and only if the original machine does. And the answer seems to be, yes, if we can modify the machine's definition so that it's no longer a standard machine but rather one with an infinite repeating pattern on the tape. Well, that's fine, so long as we recognize that it's not the same as the original system. Otherwise, we'd be requiring the input encoding to contain as many bits of the pattern as necessary, and that required number is uncomputable.

* I'm not sure if I'm being too broad in that definition - how would I restrict this to exclude the possibility of the encoding process itself simulating the machine?

You heard this on /. first

[viking80]

http://slashdot.org/comments.pl?sid=338339&cid=21104157

glass houses

[m2943]

Pratt asks: "How did an argument containing such an elementary fallacy get through
the filter?"

Proofs containing elementary errors are published all the time. Peer review is, and always has been, only a way of weeding out some percentage of bad submissions. Peer review that is strict enough to ensure that only correct papers get published would also result in the rejection of many good papers. In fact, some good papers that have advanced science have contained elementary errors.

And people who sit in glass houses shouldn't throw stones. Looking through Pratt's publication list, the first two papers I came across on a topic that I know a lot about should never have passed peer review.

Everybody who publishes makes elementary mistakes and makes a fool of himself sometimes; one should respond kindly and gracefully.

Re:glass houses

[justinlee37]

Everybody who publishes makes elementary mistakes and makes a fool of himself sometimes; one should respond kindly and gracefully.

Amen. Let's eat!

Re:glass houses

[SuiteSisterMary]

Besides, an elementary error in step one or two doesn't invalidate the theory that leads to your result; of course, it invalidates the actual result.

But one has to wonder how many scientific breakthroughs were started with a 'Ooops, how silly of me...but wait a minute...

Re:Alex Smith is the next Slava Pestov?

[Shokaster]

God - no!

Words have meanings, dammit

[UnixUnix]

I confess I can't wait to read FOM in the next few days and see the reception Wolfram's letter receives... Don't get me wrong, Stephen W. has done a lot of good for Mathematics, but this is different. It is deceitful to hijack terminology with a settled, fixed meaning... and the term "universal Turing machine" is just that. And, may I add, lots of members of FOM have worked on these matters for a lifetime. Indeed, the moderator, Martin Davis, has written well-known textbooks in the field, has done research...and WAS a member of the Committee...and WAS NOT consulted about the decision! Turing machines with infinite initial conditions, or maybe operating on infinite tape-contents, possibly for an infinite number of steps, ARE interesting -- you can find some information already in the Rogers textbook, and there has been a lot of work in these and similar matters, generalizations to hyperarithmetical sets, Pi-1-1 sets, recursion on admissible sets etc... catch-all term: "higher recursion theory". BUT, this does not alter the standard meaning of universal Turing machine, for plain, standard recursion theory - and THAT is a finite control, operating on a TM description, finite of course, and a finite TM input, on an otherwise blank tape. Wolfram is free, to be sure, to define a notion of "Wolfram universality", and prove things about it; but it is misleading to claim that the results have something to do with universal TMs. Barring a _proof_ that they do! :-)

Re:Words have meanings, dammit

[evgalois]

From the FOM list: 1. Concerning the prize committee, we did not expect them to go through the details of the proof but to support the reviewers on technical issues related to their fields of expertise. We would have been delighted to have had them spend more time on the proof but that wasn't our expectation. We did talk to people about how to set the prize up. Basically we needed judgement about their areas and we were very careful to cover those that could come up in a universality proof. We are grateful to the committee for covering those areas and we are happy that they were more active than many such committees. In the review process, committee members agreed with the Wolfram Science internal reviewers, while others asked for additional clarifications (such as fulfilling universality basic requirements for non-halting machines). All committee members had Alex Smith's proof in hand for a couple of months. But it was Wolfram staff who did the hard work to achieve a satisfactory level of verification (between revisions and revision requests), and we thought that by waiting any longer we would not have learned more. It helped that a lot of the proof was submitted in the form of programs that could be run and analyzed in a systematic way. Smith's proof is available to everybody, anyone can point out anything, and it is nice to get the sense that there are people out there who would be interested in verifying proofs. This is great news, and if we do other prizes we would definitely like to take advantage of that. We would be also delighted to hear opinions on how to set up next prizes. 2. Concerning the definition of universality, a halting state or halting instruction wasn't a requirement. This is a common usage nowadays in the field of small universal Turing machines (see detailed references below), which is a generalization of previous definitions. If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear. However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape). So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort. The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. One could fairly argue that two non-universal coupled automata can reach universality, but it would require the couple to interact at every step, as in Margenstern's nice example [1], but that's very different from a non-universal second automaton intervening only once at the first step. People using universality generalizations of this sort: [1] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, November 1996. [2] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, vol. 2295 of LNCS, pp. 311-318, Vienna, May 2002. Springer. [3] Maurice Margenstern and Liudmila Pavlotskaya. On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation, 13(2):133-202, April 2003. [4] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pp. 1-10, Chisinau Moldavia, May 2001. Springer. [5] Turlough Neary and Damien Woods. Four small universal Turing machines. Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pp. 242-254, Orleans, Fran

Re:Words have meanings, dammit

[UnixUnix]

>If there is no clear definition is because there is no clear-cut, established procedure to determine when an initial condition is computationally simple enough to be acceptable. Some would wish universal computation stick to a finite initial condition with an unbounded tape filled with "blanks", because that's the only case where the theory is entirely clear.

Uh, no -- THAT is THE case envisioned by ordinary recursion theory. That is the meaning the TECHNICAL TERM "universal Turing machine" has. If "something else" is "universal" in some other sense, fine -- but please, CALL IT SOMETHING ELSE! (Whether it helps sell a book or not :-P )

How do I explain this?! Example: it might be reasonable to call a function from the reals to the reals "continuous" if it assumes "all the in-between values" -- that is, for any a and b, for any t between f(a) and f(b) there is an s between a and b such that f(s) = t. Unfortunately, there already exists a familiar, epsilon-delta definition of "continuous" that turns out to be non-equivalent to the previous one (indeed, stronger). You cannot, then, say "continuous" and mean the _former_ definition... just because it "sounds reasonable"! OK? "Continuous" is a technical term. So is "universal Turing machine"!

>However, others accept generalizations such as periodic "blank" words as long as they remain computationally simple enough (possibly generated in the same fashion as an unbounded "blank" tape).

You don't have to "generate" an unbounded blank tape, you simply assume it contains "blanks", in other words, anything BUT your symbols for "0" and for "1". And you don't have to prepare anything infinite -- "unbounded" means at any step you might have to make available one more tape square. If the machine "never halts", it will be using longer and longer finite stretches of tape, forever. At no moment will it have "used up infinitely much tape".

Preparing an infinite tape, with whatever contents, is beyond the pale of ORT (ordinary recursion theory). I myself said, it IS done, itself and other, more complex things -- but when we do it we do not call it ORT. It is something else.

>So Alex Smith's use of a non-periodic but still sufficiently computationally simple background is a natural generalization of this sort.

Fine -- so call the result "a due generalization of so-and-so"! Something universal in a certain specified sense, "W-universal" or something.

>The key point is that the background can be set up without doing universal computation, so the 2,3 machine itself actually carries out the computation. One could fairly argue that two non-universal coupled automata can reach universality, but it would require the couple to interact at every step, as in Margenstern's nice example [1], but that's very different from a non-universal second automaton intervening only once at the first step.

What do you mean by "not doing universal computation"... or similarly for the coupled automata? Let me discuss the latter -- it IS known that any Turing machine can be simulated by two appropriate PDAs (Pushdown automata) ...quite obvious; two stacks simulate a tape, i.e. moving the TM head one square along the tape becomes popping a symbol off one stack and pushing it onto the other. In particular, any universal TM M can be simulated by an appropriate pair of PDAs, A and B. But there is no sense in "dividing up universality"; neither A nor B is universal...since no PDA can be a universal TM. It sounds like you are treating universality as if it were mass, or a measure of sorts, as if A + B being of measure 1 and A of measure 0 means B is of measure 1. Where is this coming from?! It makes no sense!

The definitions and results of ORT are precise...but also hair-thin. Even a seemingly innocuous change can have drastic effects. [Quick example: suppose you impose on TM's that their input be read-only... the rest of the tape is available for read-write as usua

Re:Words have meanings, dammit

[evgalois]

Your example of PDA's would require to have them interacting at every step as was said in the FOM list from where everybody is jumping to wrong conclusions. Smith's proof does not suppose any communication.

Re:duh

[meringuoid]

Oh, I see. A Universal Turing Machine was just the development codename for VMWare. Gotcha.

Essentially true, though. Any computer can emulate any other computer, as long as it's given enough memory.

Rejecta Mathematica

[malilo]

I don't know if it got off the ground, but at Rice U. the grad students recently funded a project called "Rejecta Mathematica" for just such a purpose - the publishing of failed/rejected papers! I thought it was a good name, at least. Ok, for fun I googled it, and they are taking submissions for their inaugural issue: http://math.rejecta.org/

official != correct

[dazedNconfuzed]

"The status of some machines will necessarily change from 'non-universal' to 'universal'"??? This sounds like a cop-out to justify the error in the proof: re-define the problem so the proof fits it.

Sometimes the official definition of a boundary (in this case, the difference between non-universal vs. universal) is, upon careful inspection, found to be wrong/incomplete/complicated/obfuscated. The indicated post indicates that the mathematical understanding of "universal" is understood to be incomplete; apparently the 2,3 machine is exposing just such a flaw (and sometimes just discovering a problem is worthy of a Nobel Prize).

Indeed, that's the biggest problem with software engineering: specifications which appear complete usually aren't. Analyzing and modifying and correcting incomplete specs isn't a cop-out.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Alex Smith is the next Slava Pestov?

[bcat24]

That's quite interesting, Mr. Smith.

DUDE YOU MADE MY DAY!

[tjstork]

Thanks for taking a few minutes to educate me as to these things. You made my day!

Re:DUDE YOU MADE MY DAY!

[sydneyfong]

Duh.

It was previously (in 2002) mentioned on slashdot

Your UID is much lower than mine, so I suppose you were already here.

Re:DUDE YOU MADE MY DAY!

[tjstork]

You know what though, I still think FACTOR is NP-COMPLETE. Is there a proof otherwise?

Re:DUDE YOU MADE MY DAY!

[sydneyfong]

Never heard of any proof, but here's some evidence:

FACTOR can be done in P for quantum computers. http://en.wikipedia.org/wiki/Shor's_algorithm
NP-complete problems are still known to require exponential time on quantum computers.

Also if you really understood NP-complete problems, most of them require finding a particular combination/permutation (of "stuff") to match the problem criteria. However, factoring is mathematical. The two types of problems simply "feel" different.

You might also want to take a look at:
http://en.wikipedia.org/wiki/Integer_factorization_problem#Difficulty_and_complexity

Wow

[JCSoRocks]

I knew slashdot was full of nerds... but this is ridiculous. Can we at least get some Apple / MSFT, Linux / Windows, XBOX / PS, bashing in here to spice things up?

What about Hart's 2,3 TM?

[glwtta]

Ok, yes, I am a giant dork.

PARENT IS ONLY POST IN THREAD WORTH READING

[CaptainPinko]

Thank you, hope you get modded up, if I had mod points I'd do it myself.

Do the Walk - THEN you can talk

[hung_himself]

This entire thread is a demonstration of why we have things such as peer reviewed journals and why people don't (or shouldn't) take results seriously until they have been published.

At least then we are sure that some (somewhat) impartial experts in the field have looked at it and deemed it sound. At least then we have a starting point for discussions. Now all we have is some guy from Wolfram telling us that their definition is the right one and that they spent a lot of time on this and don't talk to us about it unless you understand the thread.

Publish it somewhere reputable and then this discussion is worthwhile - but until then no one has the time, even on /. to waste on evaluating press releases.

2 Sided Issue

[Val_0]

I am no math wizard and a lot of this problem is over my head but I still have been following the developments since the prize winner was announced. I believe that what is happening now with the controversy of the issue is exactly what should happen if the scientific process is working. The kid is very talented and had enough courage and determination to submit his proof. Just because someone submits a proof it doesn't automatically make it correct. That is why it gets reviewed by the peers and during this process errors get caught and changes are made. No matter which way the issue is resolved it will still progress the mathematicians towards the real answer.

Re:Summary for Average Joe Geek

[synthespian]

Why is this modded down to *1* ?

Let my protest be known! :-)

Can anyone answer me this, though?

[Cafe Alpha]

Why the hell is Wolfram or anyone else wasting any effort on this problem. It is useless isn't it?
Or does that flake Steven Wolfram have some delusion that the universe is a 2,3 machine that is somehow simulating physics or something?

Re:duh

[halivar]

Wow. Is that really the same Noam Chomsky? I had completely bifurcated the Noam Chomsky of formal grammar theory and Noam Chomsky the liberal activist. I never before put those two together. I must be an idiot.

Thanks for the well written explanantion.

[clay_buster]

Your posting is one of the reasons I keep reading slashdot. Yet another posting I wish I had mod points for.

Re:Factoring is poly time... duh

[HuguesT]

Actually, FACTOR is in QP (there exist a polynomial algorithm for factoring, but on a quantum computer). QP is believed to be simpler than NP, but there is no proof.

Re:duh

[HuguesT]

That is the very same. Chomsky is primarily known as a linguist, though. Activism is just a hobby :-)