Slashdot Mirror
44 Conjectures of Stephen Wolfram Disproved
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."
Tim's cellular automata FAQ may be of some help in understanding all of this.
If you go to the NKS Forum, 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 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."
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.
As I understand it, it's basically an abstract-logic equivalent of a Perl golf 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)
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.
I've fallen off your lawn, and I can't get up.
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.
After all, I am strangely colored.
You can read the full text of "A New Kind of Science" online for free at http://www.wolframscience.com/nksonline/toc.html