Forgot your password?
typodupeerror
Math Science

44 Conjectures of Stephen Wolfram Disproved 158

Posted by kdawson
from the new-kind-of-error dept.
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."
This discussion has been archived. No new comments can be posted.

44 Conjectures of Stephen Wolfram Disproved

Comments Filter:
  • by Ed Pegg (613755) * <ed@mathpuzzle.com> on Sunday December 23, 2007 @03: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
    • Re: (Score:1, Troll)

      by Nimey (114278)

      That is a very inflammatory title.
      On Slashdot?. Never!
    • by jacquesm (154384)
      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.
  • by Racemaniac (1099281) on Sunday December 23, 2007 @03: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...
    • by rxmd (205533) on Sunday December 23, 2007 @03:14PM (#21799476) Homepage

      "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...
      You have assuming that the editors can reading!
    • by evanbd (210358) on Sunday December 23, 2007 @03:16PM (#21799486)
      If your shift key is broken, it is permissible to use your caps lock key for the 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.
      • Re: (Score:1, Redundant)

        by marcello_dl (667940)
        Let me disprove the usefulness of parent post for failure to assume laziness of GP poster.
      • by nospam007 (722110)
        If your shift key is broken, it is permissible to use your caps lock key for the
        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
        • by pthisis (27352)
          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.

          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!)'
          • I like Insert (vi user). It is especially handy for a Dvorak layout, where ctrl-C and ctrl-V are cumbersome. Using ctrl-ins and shift-ins for copy/paste with this layout is actually even MORE convenient.
        • Re: (Score:1, Offtopic)

          by nhaines (622289)
          Actually, that was originally the location of Ctrl. I'm not sure why the changed it, but if I were to remap my CapsLock, it would definitely be to Ctrl.

          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...).
          • by osu-neko (2604)
            I do precisely that. Control key sequences, especially the vital Ctrl-S and Ctrl-Q, are much easier to type when you put the control key back where God intended it to be. ;)
            • by und0 (928711)
              [...] especially the vital Ctrl-S and Ctrl-Q, are much easier to type when you put the control key back where God intended it to be. ;)

              Near your right pinkie? ^__^
      • Or, quit being a damn cheapskate and go pay 20 bucks for a keyboard!

        Oh, you're you on a laptop? Quit typing so damn hard!
      • by Phleg (523632)
        i switched to colemak [colemak.com], you insensitive clod!
    • Re: (Score:3, Funny)

      by rcw-home (122017)

      "has disproving" is it that hard to write a summary without such huge errors??

      One word: havening [nanc.com].

    • by flyingfsck (986395) on Sunday December 23, 2007 @03:58PM (#21799764)
      Slashdot Engrish is to be informating and not to be laughful at.
    • by rm999 (775449)
      Funny thing is, the sentence is about a person whose job (hobby?) is to look for errors in grammar.

      Look at his correction of this textbook:
      http://www-math.mit.edu/~sipser/itoc-errs2.1.html [mit.edu]
    • Re: (Score:2, Troll)

      by OrangeTide (124937)
      People on the internet are too busy typing to be bothered with reading.
    • by raddan (519638)
      Actually, I think it was supposed to be "Can has disproving!"
    • by Jugalator (259273)
      "I has disproven you"

      ^-- sounds like something from a LOLCAT image... One of those particularly serious looking lolcats.
  • by Jah-Wren Ryel (80510) on Sunday December 23, 2007 @03: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 @03:03PM (#21799408) Homepage
    Tim's cellular automata FAQ [cafaq.com] may be of some help in understanding all of this.
  • is directly proportional to the knowledge required to post
    • by hung_himself (774451) on Sunday December 23, 2007 @03: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...
      • by crosson (1204404)
        Every knows that biology is weak, and Math is strong.
        • Every knows that biology is weak, and Math is strong.
          Don't know who this Every person might be, but he/she is utterly wrong...
          • 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.
            • ...Truly, like so many of our leaders, this Every One character is simply an influential dullard.

              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.
  • by mortonda (5175) on Sunday December 23, 2007 @03:26PM (#21799540)
    when I say...

    Huh?
    • by h2k1 (661151)
      is there anyone out there willing to translate this post to dumb ass slashdoters?
      • by emurphy42 (631808) on Sunday December 23, 2007 @05: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)

        • by fyngyrz (762201) * on Sunday December 23, 2007 @05: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.

          • Perhaps Wolfram was counting the weight of "not" as zero in his mind when he constructed his table. I'm not going through the reg page to find out what he actually wrote. His error could be as small as *printing* that he was giving weight one to "not" when in fact he hadn't.

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

            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?
        • by morcheeba (260908)
          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?
        • by pongo000 (97357)
          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?
          • by fyngyrz (762201) * on Sunday December 23, 2007 @08: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.

            • Aside from a really wonderful book on fuzzy logic which to this day I know of no faults with...


              May I ask what book on fuzzy logic that was?

              P.S.
              Thanks for the polite "south end of a northbound rat" euphemism!
              • by fyngyrz (762201) *

                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.

        • 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.
        • by ratboy666 (104074)
          Thank you.

          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
          • by ratboy666 (104074)
            Sorry for replying to myself -- the fellows name is Pat Maupin. Credits to him!
  • by mathcam (937122) on Sunday December 23, 2007 @03: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!

  • by yotto (590067) on Sunday December 23, 2007 @04: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!
    • by mcg1969 (237263) on Sunday December 23, 2007 @04: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.

  • by mcg1969 (237263) on Sunday December 23, 2007 @04: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.
    • by mcg1969 (237263) on Sunday December 23, 2007 @04: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."

  • All the author does is show that 44 of the boolean equations [out the 256 3 input equations in 1-D cellular autmata] Wolfram provides are not minimal.
    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.
  • by ksw2 (520093) <obeyeater AT gmail DOT com> on Sunday December 23, 2007 @06: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]
  • by Anonymous Coward
    While I'm not surprised to see people refute some of Wolfram's claims, I hate seeing preprints distributed that have key citations that are "Unpublished results". The whole point of peer review is to treat results as believable when they can be independently verified. Citing unpublished work is a bit sketchy. It would be nice if people could wait before distributing results until proper review has taken place (but then again, this is refuting wolfram, the kind of non-peer-reviewed publication).
    • by Auckerman (223266)
      That's not completely how it works. When your working on a project, you maintain current results for others to work from. Of course, you don't let them know everything you know, so that you don't lose a coming grant proposal to them, but enough so that you are actually furthering the science before publishing. In the case of unpublished results, those are shown all the time, in a peer review system. Conferences, your web page (getting an email that there's a better way is something you want to have happ
  • I had all my conjectures and overtures disproved and disapproved. Big deal.

For God's sake, stop researching for a while and begin to think!

Working...