Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

44 Conjectures of Stephen Wolfram Disproved

Posted by kdawson on Sun Dec 23, 2007 01:55 PM
from the new-kind-of-error dept.
Math Science
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."
+ -
story

Related Stories

Submission: MIT Student disproves Stephen Wolfram by Anonymous Coward
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

44 Conjectures of Stephen Wolfram Disproved 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • Slightly different boolean formula (Score:3, Interesting)

    by Ed Pegg (613755) * <ed@mathpuzzle.com> on Sunday December 23 2007, @02:00PM (#21799380) Homepage
    That is a very inflammatory title. The page in question is: http://www.wolframscience.com/nksonline/page-884 [wolframscience.com] Comparing the items in the paper to this page, there isn't much here.

    • Re: (Score:3, Insightful)

      by gzipped_tar (1151931)
      Yes the difference are "slight"...

      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
    • Doesn't Wolfram have a stake in that journal ?
    • The paper at the heart of this slashdot discussion deals directly with http://www.wolframscience.com/nksonline/page-884 [wolframscience.com] There are 256 boolean expressions on this page from Stephen Wolfram's book The paper claims to give 44 shorter expressions.

        • Re:Slightly different boolean formula (Score:5, Informative)

          by poopdeville (841677) on Sunday December 23 2007, @04:58PM (#21800588)
          Zermelo-Frankel Set Theory is an axiomatization of set theory. That is to say, it is a list of axioms describing properties of any structure that is meant to be a collection of sets. There are alternative structures and alternative axiomatizations to generate those structures. (FYI, a consequence of Godel's Incompleteness Theorem is that there are infinitely distinct (in a non-trivial sense) axiomatizations of the natural numbers.)

          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.
          • I confess to being a bit rusty on this subject, but isn't it the rationals that are a field? Or at the very least, you don't need to go to the reals to get a field, although they are a field...
            • Completeness in the real numbers is not that every Cauchy sequence converges, it is that every set bounded above has an upper bound.

              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:Slightly different boolean formula (Score:4, Insightful)

          by 2.7182 (819680) on Sunday December 23 2007, @07:50PM (#21801716)
          Not to be a jerk or anything, but two years of calculus and a PDE course don't prepare you to understand all that much. In this case some course in logic and the theory of computation might be in order.

  • English anyone?? (Score:4, Funny)

    by Racemaniac (1099281) on Sunday December 23 2007, @02:01PM (#21799388)
    "has disproving"
    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...

  • Watch out for the roundhouse kick (Score:5, Funny)

    by Jah-Wren Ryel (80510) on Sunday December 23 2007, @02:02PM (#21799396)
    Doesn't Evangelos know that Wolfram is the Chuck Norris of Math?
    Nobody disproves Chuck Norris and lives to publish about it!

  • More info (Score:4, Informative)

    by the_kanzure (1100087) on Sunday December 23 2007, @02:03PM (#21799408) Homepage
    Tim's cellular automata FAQ [cafaq.com] may be of some help in understanding all of this.

  • I think I speak for a lot of people here ... (Score:5, Insightful)

    by mortonda (5175) on Sunday December 23 2007, @02:26PM (#21799540)
    when I say...

    Huh?

      • Re:I think I speak for a lot of people here ... (Score:5, Informative)

        by emurphy42 (631808) on Sunday December 23 2007, @04:02PM (#21800224) Homepage

        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:

        1. T,T,T
        2. T,T,F
        3. T,F,T
        4. T,F,F
        5. F,T,T
        6. F,T,F
        7. F,F,T
        8. F,F,F

        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.

        • f(T,T,T) = F
        • f(T,T,F) = F
        • f(T,F,T) = F
        • f(T,F,F) = F
        • f(F,T,T) = F
        • f(F,T,F) = F
        • f(F,F,T) = T
        • f(F,F,F) = F

        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)

          by fyngyrz (762201) * on Sunday December 23 2007, @04:24PM (#21800364) Homepage Journal

          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.

        • De Morgan [wikipedia.org] wins again! (and the p's and q's are in exactly the same order as on the wikipedia page)

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

          So Wolfram doesn't know Morgan's rule?
        • So, IOW, careful application of DeMorgan's Theorem results in the simplification of some of Wolfram's functions.

          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)

            by fyngyrz (762201) * on Sunday December 23 2007, @07:52PM (#21801726) Homepage Journal

            Aren't the original functions and new functions still equivalent?

            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.

        • Two issues:

          • We have logical minimization algorithms already. EE's use them. Why hasn't anyone run them across Wolfram's functions? Why didn't Wolfram think to do so?
          • "Minimum number of symbols" is an interesting criteria. If you want to minimize each expression, you would have a wider set of logical operators: (p XOR q) is equivalent to (p OR q) AND (p NAND q), as well as (p OR q) AND NOT (p AND q). Using XOR instead of simply AND, OR, and NAND, or AND, OR, and NOT simplifies the expression to some extent.

  • MIT Errata Expert, eh? (Score:4, Funny)

    by mathcam (937122) on Sunday December 23 2007, @02:52PM (#21799724)
    "...so basically I'm really good at being right about things that other people are wrong about."

    Wait a minute, that's what I do!

  • That's egg on his face. (Score:4, Funny)

    by yotto (590067) on Sunday December 23 2007, @03:05PM (#21799812) Homepage
    "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."

    Oh, SNAP!

    • Re:That's egg on his face. (Score:5, Informative)

      by mcg1969 (237263) on Sunday December 23 2007, @03:24PM (#21799948)
      That's not as much of a SNAP! As you think. The reason that "simple inspection" reveals that the formulas are not minimal is because, in an earlier paper, the same author demonstrates that 5 boolean operators are sufficient. So it actually took a bit more than "simple inspection" to get there.

  • The paper is not as hostile as the citation (Score:5, Insightful)

    by mcg1969 (237263) on Sunday December 23 2007, @03:10PM (#21799846)
    The author of the article, Evangelos Georgiadis [wolframscience.com], has participated in two of the "New Kind of Science" summer schools (2003, 2005; the link above is from 2003). I must suspect, then, that he is somewhat sympathetic to Wolfram's work, and his papers are not intended to be hostile attacks. Indeed, his paper really doesn't read that way, from my perspective as an academic; it is simply a correction of errors. Indeed, if anything, this work tends to buttress Stephen Wolfram's basic point (whether it is true or not) because it further reduces the complexity of CA implementations.

    • Re:The paper is not as hostile as the citation (Score:5, Informative)

      by mcg1969 (237263) on Sunday December 23 2007, @03:16PM (#21799886)
      If you go to the NKS Forum [wolframscience.com], you can find quite a few contributions by the author of this paper, and many of them are error corrections or other disputes with the content. To try it yourself, go to the search page [wolframscience.com] and type in "Evangelos Georgiadis" into the "Search by Author" field, select "Show results as posts", and click "Perform Search."

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

  • Simple title correction. (Score:5, Insightful)

    by ksw2 (520093) <obeyeater AT gmail DOT com> on Sunday December 23 2007, @05:38PM (#21800868) Homepage
    s/Disproved/Improved/
  • You can read the full text of "A New Kind of Science" online for free at http://www.wolframscience.com/nksonline/toc.html [wolframscience.com]

    • Re:Humm... (Score:5, Interesting)

      by Omnifarious (11933) * on Sunday December 23 2007, @02:12PM (#21799466) Homepage Journal

      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)

        by ceoyoyo (59147) on Sunday December 23 2007, @02:40PM (#21799644)
        For particularly small values of "everyone" of course.
      • Likewise, the fact that Stephen Wolfram is an arrogant blowhard should not prevent people from making a reasoned assessment of his work. And that is, in my view, what seems to be happening. Sure, Wolfram is hogging some undue spotlight right now. But his work is absolutely useless unless it can be reproduced, verified, built upon, and applied by others. Give it 20-50 years and we'll see what happens. My prediction is that Wolfram's claims about the work, in particular its wide applicability, will be proven

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

      • Hey, it takes some guts to go out on a limb. ESPECIALLY in a field where your work can be "proven wrong".

        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)

          by IgnoramusMaximus (692000) on Sunday December 23 2007, @02:46PM (#21799682)

          Whose name is he supposed to hype? Yours?

          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:Humm... (Score:4, Insightful)

              by IgnoramusMaximus (692000) on Sunday December 23 2007, @04:27PM (#21800388)

              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:!Clearly the lack of posts (Score:5, Insightful)

      by hung_himself (774451) on Sunday December 23 2007, @02:35PM (#21799604)
      is directly proportional to the perceived knowledge required to post.

      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...
          • Clearly he's on a first name basis with Every One. This is good for him since as they say, you have to pretty much know Every One to get ahead in this world. On the other hand, when I ask who truly understands any complicated subject, the response is always "not Every One". Truly, like so many of our leaders, this Every One character is simply an influential dullard.
    • Proofreading? On Slashdot? You must be new here!
    • Im more interested in the mathematical errors being discussed than grammatical ones. Anyone got anything to say about these 44 conjectures or the guy who made them?

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.