44 Conjectures of Stephen Wolfram Disproved 158
Richard Pritches writes in to let us know that MIT errata expert Evangelos Georgiadis has disproved 44 conjectures set by Dr. Stephen Wolfram (founder of Mathematica) in A New Kind of Science. The paper was published in the latest issue of the Journal of Cellular Automata and can be read in PDF form at Prof Edwin Clark's collection of reviews of Wolfram's ANKS. "The formulas provided by Wolfram for these [44] rules are not minimal. Moreover for 8 of these cannot be minimal even by simple inspection since minimal formula sizes for 3-input Boolean functions over this basis never exceeds 5."
Slightly different boolean formula (Score:3, Interesting)
Re: (Score:3, Insightful)
but according to Georgiadis's paper, they're different in nature. Wolfram guess they're 'minimal' in size (plz see the Georgiadis paper for the exact definition) but they are discovered not to be so.
I'm not one in the circle of CA and I don't understand all the significance about these arguments. But I don't think disproving some conjectures are "inflammatory" in mathematics. It seems some people are not satisfied with Wolfram's style (e.g. his failure in acknowledgin/inter
Re: (Score:1, Troll)
Re: (Score:2)
Re: (Score:1)
Do not click? It's the subject of the article! (Score:2)
Re:Slightly different boolean formula (Score:5, Informative)
Since you've studied Diff Eqs, I'll give you a little example of why axioms of this kind are needed. You were studying differentiable functions. Many of their properties are due to the completeness of the real numbers. Many of their properties are due the real numbers being ordered. Some are due to the fact that the real numbers form a field. And while tools like linear algebra might be necessary to study differential equations, all the properties of differentiable functions are caused by at least one of these three (and the definition of a differentiable function).
It turns out the real numbers can be characterized as the complete ordered field. To axiomatize the real numbers -- to write sentences from which all the others follow -- we just have to group together the completeness axiom (Every Cauchy sequence converges in the set), the field axioms, and the order axioms. If, for example, you drop the completeness axiom, you would also be writing about things like the rational numbers since they're an ordered field that happens to not be complete.
Axioms aren't about truth. They have a specific meaning in logic, and more importantly act as a sign post to the audience saying: this is what I'm going to talk about, and how I'm going to talk about it. Of course, in practice, mathematicians don't explicitly state these axioms unless they are the subject of the paper. But they are implicitly "contained" in the jargon.
Re: (Score:1)
Re: (Score:2)
That should be "has a LEAST upper bound."
That real Cauchy sequences converge follows from this property, but not the other way around.
False. One way to construct the reals is to consider equivalence classes of Cauchy sequences of rationals. The reals constructed in this manner have the least upper bound property.
For an example take rational functions as your field wit
Re: (Score:1)
Re: (Score:2)
Furthermore, what is an open interval for these functions? Are you talking about epsilon neighborhoods with respect to some metric?
Re: (Score:2)
Re: (Score:1)
You mean a supremum, or least upper bound. Having just an upper bound is trivial, since every number is finite. The "axioms" happen to be equivalent.
http://en.wikipedia.org/wiki/Complete_space [wikipedia.org]
http://www.mathology.net/mathology/vis_articolo.asp?id=44&lang=ita [mathology.net]
To prove that they are equivalent, note that there is a bijective correspondence between elements of convergent sequ
Re: (Score:1)
First: the range of a Cauchy sequence is bounded.
Pf/ Let {x_n} be a Cauchy sequence and epsilon > 0. Then there is an N such than m and m => N implies that d(x_m, x_n) epsilon. Since N is finite, there is a maximum pairwise distance between points whose indices are less than or equal to N, denoted max_{i,j=N} {d(x_i, x_j)}. Thus the maximum distance is max_{i,j=N} {d(x_i, x_j)} + epsilon.
Second: dually to the co
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
Re: (Score:2)
Re:Slightly different boolean formula (Score:4, Insightful)
English anyone?? (Score:4, Funny)
is it that hard to write a summary without such huge errors??
i'm not a native english speaker, and it even pokes out my eyes...
Re:English anyone?? (Score:5, Funny)
Re:English anyone?? (Score:4, Funny)
Re: (Score:2)
Re: (Score:2)
No, they aren'ting.
Re: Gearge? (Score:2)
You have to spell your adversary's name correctly first.
Re: (Score:2)
Where's the probleming?
Re:English anyone?? (Score:4, Funny)
Re: (Score:1, Redundant)
Re: (Score:1)
duration of the required capital letter. I know that key is abhorrent to most here, but it does have uses in the event a sudden failure of both shift keys.
___
On every new machine I get, first thing I do is siwtch off the capslock key and redirecting it to left-shift, I assume many people do the same, so we have 3 Shifts.
BTW for the machine I got a few days ago I googled a nice utility which does it nicely, no registry hacks I ne
Re: (Score:2)
What you map it to usually depends on your editor. Emacs users map it to ctrl, vi users map it to esc.
(I've never heard of mapping shift before, and given that it's right next to a shift key that doesn't seem like a big help to me but if it helps you then do it!)'
Re: (Score:2)
Re: (Score:1, Offtopic)
On the other hand, the OLPC XO-1 is mapped that way and I haven't become used to it yet... So for now I'll leave everything where it is until I can get a nice keyboard with generic keycaps (although I'd substitute a Tux icon for a "Super" label...).
Re: (Score:1)
Re: (Score:1)
Near your right pinkie? ^__^
Re: (Score:1)
Oh, you're you on a laptop? Quit typing so damn hard!
Re: (Score:2)
Re: (Score:3, Funny)
One word: havening [nanc.com].
Re:English anyone?? (Score:5, Funny)
Re: (Score:2)
Look at his correction of this textbook:
http://www-math.mit.edu/~sipser/itoc-errs2.1.html [mit.edu]
Re: (Score:2, Troll)
Re: (Score:2)
Re: (Score:2)
^-- sounds like something from a LOLCAT image... One of those particularly serious looking lolcats.
Watch out for the roundhouse kick (Score:5, Funny)
Nobody disproves Chuck Norris and lives to publish about it!
Re: (Score:2)
More info (Score:4, Informative)
!Clearly the lack of posts (Score:1)
Re:!Clearly the lack of posts (Score:5, Insightful)
You must be new around here. When it comes to biology, everyone seems to think they are experts. Because there are so many computer people here, at least when it comes to math, more of them know that they know nothing...
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
It's because of his family (Score:2)
It's sort of expected. Every One's brother No was looking out for him, so Every One got all of the good press. When things went well, Every One claimed responsibility. When things when poorly, No One accepted the blame.
I think I speak for a lot of people here ... (Score:5, Insightful)
Huh?
Re: (Score:1)
Re:I think I speak for a lot of people here ... (Score:5, Informative)
As I understand it, it's basically an abstract-logic equivalent of a Perl golf [wikipedia.org] exercise.
Given three Boolean variables (p,q,r), there are 2 possible values (T,F) per variable, thus 2^3 = 8 possible values for the combined set:
Now consider functions f(p,q,r) whose output is a Boolean variable. Each such function can be completely described by what output it produces for each of the 8 combinations listed above, e.g.
There are multiple ways to describe the above function, but they're all equivalent to each other because they all give the same results. Thus, there are exactly 2^8 = 256 distinct functions of this sort.
Wolfram published a list of descriptions for all 256 of these functions, attempting to use the minimum number of symbols (p,q,r,not,and,or) in each case. Georgiadis pointed out that he could have done better in 44 cases. For instance, Wolfram labeled the function given above as Rule 2, and gave the intuitive 7-symbol representation
f(p,q,r) = (not p) and (not q) and r
while Georgiadis gave a 6-symbol representation
f(p,q,r) = r and not (p or q)
Re:I think I speak for a lot of people here ... (Score:5, Informative)
First of all, mod parent up. I know you moderators suck ass and the system is broken, but come on - parent post is a precise description of TFA's issue, the first in the thread. If you're going to spend mod points at all and pretend they do something worthwhile, parent post is the place.
Secondly, Wolfram's point - in the book - wasn't that the descriptions were minimal (even if he may have mentioned that he thought they were, which I don't actually recall), his point was that they were a complete set of correct descriptions (which I would add are functionally equivalent to the minimal ones anyway) that one can examine for certain behaviors he thought were significant. Niggling about the description not being minimal does not affect what Wolfram was trying to say to the reader. He may be completely wrong, but this kind of nit-picking can not and will not demonstrate it. It is a complete waste of everyone's time.
use of a conflicting basis? (Score:1)
Personally, I find it rather arbitrary to give a weight to the unary not operator. It strikes me as more fundamental (and less arbitrary) to take as your basis the set of *all* binary input truth functions.
Suppose you change your basi
Re: (Score:2)
They aren't linearly independent. The Scheffer stroke is a generator for this structure.
I hadn't heard of the Scheffer stroke by that name, but I have known nand is sufficient for a long time. For as long as I looked at this, it appeared that the game was to establish a descriptive upper bound representing three-input truth functions in terms of a chosen basis of binary-input truth functions. What is the usefulness of the descriptive bound is the value changes rather arbitrarily depending on precisely which basis one selects? What does linear independence have to do with it?
This reminds me
Evangelos Georgiadis, Math Instructor (Score:2)
f(p,q,r) = (not p) and (not q) and r
Georgiadis gave a 6-symbol representation
f(p,q,r) = r and not (p or q)
In summary, Wolfram failed to simplify the equation properly, so in Georgiadis's mind, Wolfram failed it!
I hate a nit picky math professor, but is there any other kind?
Re: (Score:2)
Re: (Score:2)
For instance, Wolfram labeled the function given above as Rule 2, and gave the intuitive 7-symbol representation
f(p,q,r) = (not p) and (not q) and r
while Georgiadis gave a 6-symbol representation
f(p,q,r) = r and not (p or q)
Re: (Score:2)
And the impact of this is...what, exactly? Aren't the original functions and new functions still equivalent?
Re:I think I speak for a lot of people here ... (Score:5, Interesting)
They are. Wolfram was saying, Look here, for each case, applying the following CA rules gets you the following output set (smaller than the input set) of behaviors. So he was observing - in another way - that the various inputs resulted in a more sparse set of results (speaking as far as they are unique with respect to each other.) Once he identified the various types of behavior possible from these sets, he showed that some were very orderly, some considerably less so, some obviously recognizable - visually - as being members of the same classes of behaviors, and some not so obvious at all except that they certainly weren't in the easy-to-recognize class.
From there - and it gets a lot more murky - he went on to propose that these very behaviors might underlay either everything, or darned near everything. To bolster that assertion, he showed that you could find those very patterns in many interesting and disjoint places - formulas seeming completely unrelated to anything he'd talked about thus far, seashell structure and so forth. That part of the book was downright breathtaking.
It's really a very interesting book. His conclusions far outstrip his ability to back them up, but as far as TFA goes, it's looking at the very start of his chain of reasoning and applying some nitpicking that changes nothing he said or meant to say that had anything at all to do with the proposals and justifications made in the book.
Personally, I could give the south end of a northbound rat if he has a high opinion of himself, or not. What I appreciate is that he provided me with a great read, thought provoking on the one hand, and as far as I could tell, without running into anything I knew that would make me question his approach or conclusions. I've got a good general science background, strong engineering and technical design skills, passable math, and am very creative; I do fairly well at finding little - occasionally large, usually not - holes in new science books and have a huge collection of such volumes full of snippy little annotations of my own (and just for my own benefit, on re-reading.) Aside from a really wonderful book on fuzzy logic which to this day I know of no faults with, this book stood out as almost uniquely solid in the specific area he was clearly trying to explain his thoughts on. I consider it money and time well spent.
Re: (Score:1)
May I ask what book on fuzzy logic that was?
P.S.
Thanks for the polite "south end of a northbound rat" euphemism!
Re: (Score:2)
The book is "Fuzzy Logic" by McNeill and Freiberger, 0-671-73843-7. I *really* enjoyed that book. I like
Southbound... that's one of my two originals. The other isn't quite as polite - when something is dead, expired, blown up, crashed, faulted or otherwise demised in a terminal fashion, I use "darn thing is nipples north" or some similar construction. Some kind of magnetic affinity happening there, clearly. :-) Feel free, it it takes your fancy.
Re: (Score:2)
The history of programming languages is quite instructive. It relates to algorithms, and possible uses.
First, we have machine code - tedious, and then assemblers (autocoders). Designed to take SOME of the burden of counting. (labels, branch targets).
Then, the idea of compiling formulas (math) -> FORTRAN. The experience of FORTRAN leads to BNF format (Backus *is* Mr. Fortran), which brings us to: COMIT and SNOBOL
In SNOBOL4, a BNF description is (mor
Re: (Score:2)
Two issues:
Re: (Score:2)
Why any particular fixed set?
Re: (Score:2)
And, I want to point out the practical application -- computer graphics. Our friends at Microsoft had decided that "ROP Functions" should be implemented by display drivers. Indeed, the "ROP Functions" were this set of 256 functions. Windows 3 days; I am not familiar if this is currently the case.
The solution? Since the target was always an Intel processor, generate machine code sequences of increasing time complexity, and, as each is generated, see if it solves one of the Functions. Since the seac
Re: (Score:2)
Re: (Score:2)
MIT Errata Expert, eh? (Score:4, Funny)
Wait a minute, that's what I do!
That's egg on his face. (Score:4, Funny)
Oh, SNAP!
Re:That's egg on his face. (Score:5, Informative)
Re: (Score:2)
Third party observer: "Aw, snap! [wikipedia.org]"
Indubitably, my brother; indubitably -- my diss is now affirmed.
The paper is not as hostile as the citation (Score:5, Insightful)
Re:The paper is not as hostile as the citation (Score:5, Informative)
I think if you read through the posts yourself you'll see his overall interest seems to be in improving the text, not tearing it down. In fact, one of the threads he created is called "Further Improvements and Errata."
Not Really (Score:1)
The author also shows that 8 of these are not minimal by inspection, since the maximum size of the minimal equations over this basis is 5.
Simple title correction. (Score:5, Insightful)
Superb, now the tag (Score:1)
Full text of "A New Kind of Science" is online (Score:2, Informative)
citation of unpublished result (Score:1, Insightful)
Re: (Score:2)
Why is this even on /. ?? (Score:1)
Re:Humm... (Score:5, Interesting)
Ahh, yes. But the great thing about math is that whether or not you have a grudge, everybody can look at the proof and see if you're right or not.
Personally, if I were a mathemetician, I might have something of a grudge against Stephen Wolfram too. An arrogant person who hypes his own name and abilities far beyond what is justified by the available material then publishes a giant tome of half-baked reasoning that everybody fawns over because of his hyped reputation.
Re:Humm... (Score:5, Funny)
Re: (Score:2)
Well, we are talking mathematicians here.
That leads me to an interesting musing, if there were an infinite number of people, would there then be an infinite number of people (even if it were still a small fraction of the total infinite number of people) capable of evaluating the theorems and proofs in Stephen Wolfram's book?
Re: (Score:2)
Wolfram had some interesting ideas, it's too bad he had to go and write a book and call it "A New Kind of Science." That's the title you let someone ELSE put on a book THEY write about your ideas, if your peers agree that they merit it.
Your own book, you call something like "Relativity" (Einstein).
Re: (Score:2)
Yes. Infinity is funny that way.
Well, my thought was maybe there was some sort of cap on the number of people who could understand mathematical concepts that was below infinity. :-)
And regarding the book's title, I agree completely. I was trying to tell a brilliant young (pre-HS age) friend when I was in college that certain titles are conferred upon you by others and you can't assume them yourself without seeming arrogant. And that was for something relatively minor like 'Unix Wizard'. :-)
What's good for the goose (Score:3, Insightful)
Re: (Score:2)
I agree wholeheartedly. The real test is not Wolfram's perceived reputation among either mathematicians or everybody else. The real test is how well his work holds up to scrutiny.
But criticizing any individual person putting his work under that scrutiny for holding a grudge is silly. It's precisely those kinds of emotional attachments which drive people to do the hard work of grinding through the theories and either proving or disproving them. It neither makes their work more or less valid.
Re: (Score:2)
Re: (Score:2)
Obviously someone who hasn't read the book...
It's not arrogant to present some of your best work as conjectures—a mathematician's term for "A wild-assed guess, but wouldn't it be interesting if it were true?"
Given that one of the implications of Wolfram's work is that you can do a lot of neat stuff with algorithms that are out of scope for conventional mathematics, many on Slashdot should enjoy reading ANKS. Among other things, committing some of his constructions to code is fun.
Re: (Score:2)
I have a lot of respect for the guy for trying, and for getting SOME of it right. That's more than 99% of the slashdot readers! Where would we be if it weren't for the brave few who publish their works for peer review?
Re:Humm... (Score:5, Insightful)
Nobody's.
And no hype either.
That is because the supposed subject of all this is Science. And hype and personality cults are to science as money is to politics: corrupting, destructive, counter-prodctive forces.
Reason, peer review, rigourous analysis, unassailable demonstration of proof, etc are the ways of science, not ascension to prominence via grooming oneself for mass-media "stardom" by boggling the "minds" of the rather feebly-minded general public.
Re: (Score:1)
Re:Humm... (Score:4, Insightful)
The fact that various people continuously try to remodel Science into a contest of egos and popularities does not change the fundamental fact that Science itself is in the long term immune to such tactics.
And those who attempt it end up, sooner or later, with the only scientific title they deserve: "Crackpot", their "theories" having been ground into dust by the slowly, unglamorously, mundanely, steadily turning wheels of the scientific method.
Re: (Score:2)
You are confusing fame which comes about as a result of a peer-reviewed, rigorously tested but nevertheless astonishing discovery and attempts to force acceptance of your "theories" via appeals to the mass-media audience. Then there is also simple "popularization" of science, i.e. recasting complicated discoveries in terms more palatable to the public, which is what Sagan was all about.
Fame and efforts at popularization are not a problem. Attempts to use a personality cult to bypass the peer review process
Re: (Score:2, Troll)
Re: (Score:2)
Re: (Score:2)