Slashdot Mirror

← Back to Stories (view on slashdot.org)

Paterson's Worms Solved by Number-Crunching

Posted by michael on from the get-a-bigger-hammer dept.

An anonymous reader writes "Thirty years ago, Martin Gardner described Paterson's Worms to the world. Just recently, Benjamin Chaffin, one of the designers of the Pentium 4 chip, managed to trace a couple trillion steps of the 'unsolved' worms, and has pretty much solved all but two of them."

112 of 173 comments (clear)

  1. Worms? by No_Weak_Heart · · Score: 4, Interesting

    Did somebody say worms?

    1. Re:worms? by Doomrat · · Score: 1
      C64? Why would you associate that game with the C64? I'm certain that the most primitive version was on the SNES, way out of the C64's league.

      Only game called Worms on the C64 would have been the crappy efforts of BASIC coders creating Snake clones.

    2. Re:Worms? by God!+Awful+2 · · Score: 1

      The idea sounded cool, but I looked at the webcam and all it was was a white square.

      -a

      --
      /. users can't
    3. Re:worms? by kisrael · · Score: 1

      For the record, there was a game called "Worms?" for the C=64 and Atari by Electronic Arts in 1983. It was the game described in the article, where you would tell worms what to do when they encountered a "novel" situation in terms of their hex grid. Unfortnately I can't find a link.

      Nothing to do with the "Worms" games that came out for PC and various consoles later.

      --
      SO YOU'RE GOING TO DIE: The Comic for Dealing with Death
  2. Chaffin solves Patterson's Worms... by Anonymous Coward · · Score: 2, Funny

    Sounds painful...

  3. Of course, my first reaction was by digital+bath · · Score: 1, Funny

    ...how the hell did he have the patience to step through "a couple trillion" lines of code in a worm???

    Then I read the article. These worms, then - they're basically more complex versions of the Game of Life, right?

    --
    find / -name "*.sig" | xargs rm
    1. Re:Of course, my first reaction was by way2trivial · · Score: 2, Informative

      john conmway, the other name in the opening, I believe was the inventor of life.

      --
      every day http://en.wikipedia.org/wiki/Special:Random
    2. Re:Of course, my first reaction was by flynt · · Score: 1

      john conmway, the other name in the opening, I believe was the inventor of life.

      No, that was God. Wait, John Conway *is* God!

    3. Re:Of course, my first reaction was by cliffy2000 · · Score: 1

      "john conmway, the other name in the opening, I believe was the inventor of life."
      Actually, I'm pretty sure that distinction goes to God. (or for us atheists, the pseudo-random synthesis of amino acids)

    4. Re:Of course, my first reaction was by John+Courtland · · Score: 1

      You can argue the same in a different manner, by stating that since all mass contains quanta, and all quanta is affected by all seperate quanta that interacts with it, nothing involving mass or energy (since mass IS energy) happens by chance. (Oversimplification, go look up quantum mechanics if you're truly interested).

      --
      Slashdot is proof that Sturgeon's Law applies to mankind.
  4. trippy by cr@ckwhore · · Score: 4, Funny

    After reading the article, I'm left scratching my head about what this really means and how it might be useful in every day life.

    The obvious answer is that the worms are psychodelic. Those are some "trippy ass worms", as can be concluded from the illustrations in the article. Those worms are on acid.

    --
    Skiers and Riders -- http://www.snowjournal.com
    1. Re:trippy by Listen+Up · · Score: 1

      Not all research and discovery will directly impact your life. Most of the theoretical discovery and research is simply done for the sake of completeness. Puzzle pieces building a larger, complete understanding of science. In a way, solving this puzzle may not directly affect you, but it will give a more complete picture of the greater puzzle and understanding, and it's completion may indirectly influence another discovery which may lead to the creation of something that will directly relate to your life.

      And doing mathematics for the sake of mathematics is beautiful all in itself, for it is the understanding and basis of all science. Without mathematics, there is only observation.

  5. Or... by TheSpoom · · Score: 5, Funny

    Another great background for that monitor that can do 30000x40000.

    --
    It's better to vote for what you want and not get it than to vote for what you don't want and get it.
    - E. Debs
    1. Re:Or... by Doomrat · · Score: 1

      And the graphics card with 5000MB of RAM.

    2. Re:Or... by Doomrat · · Score: 1

      No, you're still working it in bits. RAM needed = 40000x30000x16/8 = 2343750KB = 2288MB

      You need to divide your answer by 8.

  6. Worms and computers by Anonymous Coward · · Score: 1, Informative

    A good overview can be found in
    B. Hayes "In search of the optimal scumsucking bottomfeeder", American Scientist vol. 91, no. 5 pp392-396 (2003)

  7. It is my belief that... by cliffy2000 · · Score: 4, Insightful

    Brute force is killing thought. We do not learn from randomly testing cases. The scientific method has degraded to the point of oblivion.
    Apparently, Frank Herbert was wrong. Brute force is the mind killer, not fear.

    1. Re:It is my belief that... by dekashizl · · Score: 5, Insightful
      Brute force is killing thought. We do not learn from randomly testing cases.
      It is an interesting point you bring up, but I think there is a lot we can learn from brute force approaches to problem solving. Your mind, in a sense, employs brute force approaches to many of its tasks. It just so happens that the billions of cycles happen in parallel rather than in serial, and the algorithms are a bit different than the ones we're used to.

      When you read this post, aside from thinking how brilliant it is, various small parts of your mind are frantically pattern matching millions of visual features simultaneously, and your "attention" is focusing a higher level consciousness onto part of that field, at which point millions of more patterns are being matched against the results of that first run, where you see letters and words, and those get matched against millions of words you've seen before, etc. etc. Brute force is everywhere around you. It is thought.
    2. Re:It is my belief that... by lawpoop · · Score: 3, Interesting

      Brute force, aka trial-and-error, is what drives evolution. Brute force created the human brain, your mind, and thought.

      --
      Computers are useless. They can only give you answers.
      -- Pablo Picasso
    3. Re:It is my belief that... by shostiru · · Score: 1
      Well, yes and no.

      From time to time I would pick up the original article and attempt a proof that a given worm would terminate or repeat infinitely, and not get very far, and I'd hoped someone else would succeed. And in general, I am concerned that the best AI we have often amounts to "do something extremely stupid as fast as possible and hope you get lucky".

      But in this case, I'm not sure it applies. Many very simple equations produce incredible complexity when you repeat them often enough ... the canonical example I learned was

      z' = cz(1-z)

      (or the more familiar z' = z*z-c, which produces the Mandelbrot set if you iterate c across the complex plane and start z at 0). In some cases you can predict the type of attractor you'll wind up with (and I don't recall the taxonomy, it's been well over a decade), or what the basin of attraction will be, but in the general case you can't (as I recall that's been proven but I could be wrong, like I said it's been awhile).

      So while I agree with you in general -- that brute force is a stupid way of solving problems and just goes to show how long we have to go with AI) -- Patterson's worms may fall into the set of problems for which brute force is the only approach to a solution (proof of this is left as an exercise for the reader).

    4. Re:It is my belief that... by Mooncaller · · Score: 1
      Bullshit. Kepler used brute force to derive his 13 laws of planitary motion ( 10 of wich were wrong). Newton then placed the three correct laws on a mathamatical foundation. Most of Chemistry was based on Brute Force investigations. The Edison Light Bulb was a brute force invention.

      Just some examples off the top of my head. There are many more.

    5. Re:It is my belief that... by No_Weak_Heart · · Score: 1
      Brute force is killing thought.

      If that were true, then Slashdot would be dead by now - killed off by the brute force attacks of frist potsers, rabid flamers, off-topic lamers and immeasureable quantities of unqualified stupidity.

      We even won't mention the speling and graammar.

      Definately.

    6. Re:It is my belief that... by SheldonYoung · · Score: 1

      Brute force is allowing certain types of problems to be solved trivial, freeing up mathematical minds to concentrate on other problems. There is no shortage of problems for us to be clever about.

    7. Re:It is my belief that... by DarkSarin · · Score: 4, Interesting

      nah...
      evidence indicates that it is not brute force that the mind uses, but rather hueristic pattern matching, followed by brute force. There is a huge difference.
      It also allows for some rather incredible pattern matching and unbelievably stupid mistakes on the part of humans.

      One of the more interesting things is that humans don't search for an exact fit when doing pattern recognition, they go for a "good enough" condition. (Rembeber teh atrilce on raeidng?) This actually allows for more rapid processing, but opens the door for some pretty stupid mistakes.

      On the whole, though, the human mind is an incredible processor. It is also non-binary, since many nerves can exist in many different states, some of which are qualitative, and it is non-linear, and parrallel! Branches, forks, etc., are quite common, and each nerve connects to a LOT of other nerves.

      --
      "We don't know what we are doing, but we are doing it very carefully,..." Wherry, R.J. Personnel Psychology (1995)
    8. Re:It is my belief that... by Vireo · · Score: 2, Insightful

      In the case of cellular automata such as Patterson's worms, it is unclear if their future states can be deduced without sequentially applying the rules (brute force resolution). For some set of rules, analytical deduction alone can solve the problem, but for others, it is believed that brute force is the only way to predict what pattern will be generated. See Stephen Wolfram's book "A New Kind of Science" if the topic interests you.

    9. Re:It is my belief that... by the+uNF+cola · · Score: 1

      Sometimes, brute force solves things on a small scale anyhow. It IS a valid solution.

      Especially when problems are "hard", the time it takes to brute force is faster than it it is to find a better solution than you had before. Besides, for some problems, there still is a problem of proving that your solution is "best".

      In programming languages, quick sort is still a very valid solution not because it has n log n best time, n^2 worst, but because they can pre-manipulate some of the stuff so the worst case is a lot better than n^2. Read up on choosing a pivot value and medians. There's a way of doing it in n time, where n is quite small and insignificant... especially while merge sort's merging code can invoke further overhead.

      --

      --
      "I'm not bright. Big words confuse me. But Wanda loves me and that should be enough for you." - Cosmo

    10. Re:It is my belief that... by pVoid · · Score: 1
      There is brute force as a means to an end, and then there is brute force as the end.

      Let me illustrate: DNA based computers (of which btw I haven't heard in a long time - Slashdot?), or even quantum computers for that matter, will generate every possible solution after which a mechanism will select the only good one.

      That is brute force as an implementation, a means to an end. Because ultimately what we are trying to reach with these computers is to implement some higher level language.

      I personally agree with the grand-parent post, in that science used to be about brilliant minds who would find very qualitative results by pure thought. My personal favorite was Richard Feynmann's proof of all of Kepler's gravitational laws by using simple euclidean trigonometry.

      Ultimately when I was reading the article, I was left wondering: if this guy is such a hot shot, why didn't he try to prove something mathematically, or short of that make a conjecture to be proven maybe 2 centuries from now (like Fermat's last conjecture). What's the value of running billions of cycles on an FSM? It completely short circuits the thought process.

    11. Re:It is my belief that... by pVoid · · Score: 1
      I think you confuse observation, and sample acquisition with brute force.

      I hardly doubt Kepler sat down, took his 2000 observed (x,y) planet coordinates, and started crunching on a list of rules:

      x = ln y false

      x = ln y^2 false

      x = ln y^3 false

      ...

      ax^2 = by^2 + k true

      "EUREKA, I've found rule number 5!"

    12. Re:It is my belief that... by Alinabi · · Score: 1

      Chemistry was based on Brute Force investigations

      Maybe that's why chemistry is still a protoscience...

      --
      "You can't allow somebody to commit the crime before you detain them." [Condoleezza Rice]
    13. Re:It is my belief that... by cookd · · Score: 1

      First, he is going for the best way for him to find the solution. The objective isn't always to challenge yourself -- sometimes you actually want to solve the problem. And if you're better at programming than numerical analysis, then you're more likely to find the solution through programming.

      Second, finding a good way to brute-force this solution isn't trivial. With that many billions of nodes to trace through, it takes a good bit of effort to find a way to optimize it enough for a computer to chew through in a reasonable amount of time. With almost a trillion nodes, you've got to be relatively clever to find a way to manage that much data without seriously crimping the computation speed.

      Third, there are some problems that don't have any better solutions. Remember the Halting Problem? Church's thesis? That time your wife/girlfriend asked if she looked fat?

      --
      Time flies like an arrow. Fruit flies like a banana.
    14. Re:It is my belief that... by Usquebaugh · · Score: 1

      Chemistry is just practical physics.

    15. Re:It is my belief that... by addaon · · Score: 1

      No, don't see Wolfram's book A New Kind of Science, as it's illiterate trash. But for the best non-introductory material on the subject, read Wolfram's academic works; much, much more readable, focused, and interesting.

      --

      I've had this sig for three days.
    16. Re:It is my belief that... by mcpkaaos · · Score: 1
      it is not brute force that the mind uses, but rather hueristic pattern matching


      Go check the posting history of any average Slashdotter, then come back and say that again.

      Shamefully, you could start with mine.
      --
      It goes from God, to Jerry, to me.
    17. Re:It is my belief that... by Qrlx · · Score: 1

      Pnysics is just natural philosophy.

    18. Re:It is my belief that... by azaris · · Score: 1

      Brute force is killing thought. We do not learn from randomly testing cases.

      I agree that random testing of cases doesn't solve anything. But there are problems that can be solved by reducing the problem to a set of special cases which can then be checked by a computer to verify our claim. The magic tour problem for 4k x 4k boards was proved this way.

      Of course, mathematicians usually prefer a completely analytic solution, like was the case with the computerized proof of the 4-color theorem.

    19. Re:It is my belief that... by Zwets · · Score: 1
      This is an emergent phenomenon, like The Game of Life and Langton's Ant.

      Emergence basically means that we can't predict ahead of time what will happen, we have to 'see it through all the way'. Many higher-level processes in the universe are emergent phenomena (life, for one thing), which is one of the reasons why we'll never be able to predict the future.

      So if you're trying to prove a mathematical theorem, I might agree that brute force could make you lazy (I'm a computer scientist though - so probably not :-), but in this case, there's no other way.

      --
      One of the lessons of history is that nothing is often a good thing to do and always a clever thing to say. - Will Duran
    20. Re:It is my belief that... by dr_canak · · Score: 1

      And I'm no expert on CA or Wolfram, but i believe he contends that you can't predict what patterns will be generated at all from theses simple rule sets. That was the whole point.

      There is a good intro article about Wolfram in this months's "Skeptic" magazine

      http://www.skeptic.com/

      And I believe it was Wolfram who started Mathematica, the same program this guys used to solve these worms. Pretty cool i think.

      jeff

    21. Re:It is my belief that... by MGS+Hartman · · Score: 1

      brute force is a great tool, if used with intelligence; you thrash it till it breaks, fix it, goto loop;

      like lou read once said: always go for overkill

      or others have said: we shall overkill.

    22. Re:It is my belief that... by MGS+Hartman · · Score: 1

      arrgh, lou REED.

    23. Re:It is my belief that... by PurpleBob · · Score: 1

      What in the world are you talking about?

      How is the halting problem brute force? It's proven using a very short, elegant proof.

      How is the Church-Turing thesis brute force? It's nothing but an assumption that allows us to make statements in computer science. Church didn't go around to a bunch of computers saying "Yep, this one only computes things that are Turing-computable... so does this one... so does this one..."

      And of course, if you use brute force on your girlfriend, then you really suck.

      --
      Win dain a lotica, en vai tu ri silota
    24. Re:It is my belief that... by Epistax · · Score: 1

      Brute force can be very important. Brute force is basically having the answer in the back of the book to a very hard problem: It doesn't help you actually solve for the answer, but once you reach it, you'll be confident in your result. This, as oppose to veryifying a bunch of results which may not be true, and verification may well take longer to do than the original problem.

    25. Re:It is my belief that... by whereiswaldo · · Score: 1

      Brute force is allowing certain types of problems to be solved trivial, freeing up mathematical minds to concentrate on other problems. There is no shortage of problems for us to be clever about.

      Good thinking, that makes sense.

      If we can actually *prove* some theories to be fact, we have a much stronger foundation to build other theories on top of. Without the brute force capabilities of computers, many theories would not never be completely resolved and thus the higher level theories based on those would have inherited their ancestor's weaknesses.

    26. Re:It is my belief that... by Tim+C · · Score: 2, Insightful

      This actually allows for more rapid processing, but opens the door for some pretty stupid mistakes.

      Indeed. I dread to think how often, when writing a report or essay, etc, I've read and re-read it while proof-reading it, and every time I've missed the fact that I've missed out a word in a sentence - something non-essential, like "the" or "and".

      My brain expects it to be there, as it fits the pattern of the sentence, and so it just fills it in for me as I read through, so I don't notice that it's missing.

      --
      It's official. Most of you are morons.
    27. Re:It is my belief that... by cookd · · Score: 1

      They state that there are some questions that can only be answered via brute force.

      And there is no right answer if a girl asks you if she looks fat, brute force or no...

      --
      Time flies like an arrow. Fruit flies like a banana.
    28. Re:It is my belief that... by cookd · · Score: 1

      Wrong. Actual conversation:

      G: Does this make me look fat?

      B: No.

      G: No, really, tell me what you think.

      B: Of course it doesn't. You look great.

      G: Tell me what you really think.

      B: I did. You look awesome.

      G: You don't have to be nice. Just give me your honest opinion.

      B: I did. You look great. If anything, you're too skinny.

      G: You're just saying that. What do you really think.

      B: (Puzzled. "No" doesn't seem to be working. Maybe it is the wrong answer? Never can tell with girls.) Umm, ok, fine. It makes you look fat.

      G: You jerk! I'm never talking to you again!

      B: ????

      --
      Time flies like an arrow. Fruit flies like a banana.
    29. Re:It is my belief that... by DarkSarin · · Score: 1

      hmmm,
      actually, looking at the posting history for myself, I have to say that it is the use, rather than the absence of, hueristics, that has led to rather stupid posts.

      Or maybe, YOU CONSIDER THIS TO BE BRUTE FORCE? That seems to be the most common form here.

      --
      "We don't know what we are doing, but we are doing it very carefully,..." Wherry, R.J. Personnel Psychology (1995)
  8. Other sites by goddess_warshipr · · Score: 5, Informative

    There are more pictures at Benjamin Chaffin's page.
    There is more information on the games and rules at Sven's page, that includes a comparison of Chaffin's notation to Gardner's and a comparison of Worms to the Game of Life.

    --
    The sky is green, the grass is blue.
    1. Re:Other sites by ratfynk · · Score: 1

      Here is another to take care of worms <UL> <a HREF=http://www.myvitanet.com/eardrag150ca.html</a >

      --
      OH THE SHAME I fell off the wagon and use sigs again!
  9. Brute Force by Anonymous Coward · · Score: 3, Insightful

    This isn't much of a solution, in particular he can only say that some worms "appear infinite" and he couldn't prove that two worms were identical except for being rotated by 180 degrees. While his programs would be useful to an individual studying the worms to try form conjectures regarding symmetry and halting they should not be confused with real solutions. Understanding should be the first aspect to any solution.

    1. Re:Brute Force by nusuth · · Score: 1

      Well, he weren't able to prove or disprove two worms were finite but for other ones, he did prove they were identical except for being rotated versions of each other. I understand that you expect a proof of the form "blah blah blah hence these two worms are identical QED" nevertheless "I run both programs, they produce the same output before terminating except for their output being rotated" is a very stong proof.

      --

      Gentlemen, you can't fight in here, this is the War Room!

    2. Re:Brute Force by isorox · · Score: 1

      Understanding should be the first aspect to any solution.

      No, the solution is to throw more and more resources into the void and hope something useful comes out. Like Social Security, or Iraq.

  10. Quantum computing by DigiShaman · · Score: 1

    ...is what will really put brute force processing to shame as we know it.

    --
    Life is not for the lazy.
  11. You are mistaken by Caractacus+Potts · · Score: 2, Interesting

    The brute force solving of problems can be very useful. The scientific method relies on theories, and having ample data to look at helps people understand complex systems, sparking the intuition that leads to more theories, and hopefully, more elegant solutions. I've worked on the optimization of large systems, and nothing helped me understand the processes involved as much as "brute force" simulations.

    1. Re:You are mistaken by tintruder · · Score: 1
      To some point, I agree, however "Brute Force" has the ability to yield results which are trusted based on the complexity of the algorithm and the enormous number of iterations.

      This trust in the machine and the associated lack of hands-on computation and evaluation of the intermediate results (instead just wait for a result to pop out)allows faulty logic or programming to gain credibility based upon the mass of the process rather than the accuracy of the result.

      If a researcher does not have the skills to perform the computations to conclusion without brute force, does the researcher necessarily have the skills to write a functional and correct algorithm? Does brute force mean the death of innovative and elegant computational innovations?

      For instance, a basic calculus student learns simple integrals such as area under a curve and learns to deliver an accurate result based upon an elegant computational tool.

      The same problem solved by a computer, even in simplest form, is indeed brute forced by repeated calculation of individual slices under the curve.

      If the human were to use the computer's method, the calculations would run pages and pages as each slice is individually processed.

      Thus does the present crop of mathmeticians pursue the elegant solution of developing methods which give acurate answers (i.e. integration) or do they look less at the theory and relationship of numbers and simply develop iterative algorithms?

      This is roughly analogous to the curent state of auto repair where the technician plugs in a computer diagnostic and then replaces the component module rather than examine the car and use a developed process of logic and intuition to arrive at the result.

      Pretty amazing how so much theory of mathematics was developed before electricity!!!

    2. Re:You are mistaken by OneEyedApe · · Score: 1

      Actually, some advanced mathematical systems would probably use symbolic logic, and solve the equation much as a human would, in those cases where the equation could actually be integrated (not all can be).

      --
      Life sucks, but death doesn't put out at all....
      --Thomas J. Kopp
    3. Re:You are mistaken by vidarh · · Score: 1
      If I don't have the skills to produce an equation that will give me the shape of a specific point of the Mandelbrot set without brute force, does that mean I don't have the skills to calculate the Mandelbrot set correctly?

      The calculations for the Mandelbrot set are trivial to do by brute force. Yet to my knowledge there are no known solutions that will tell you for an arbitrary point whether or not it will terminate before a specific number of iterations without knowledge of other points in the set.

      There are lots of rules you can use to speed up the calculations, some quite complicated. Yet all they boil down to are ways of pruning the number of points you brute force.

      So while I can't "perform the computations to conclusion without brute force" (and neither can you), I can most certainly write a functional and correct algorithm that will compute the Mandelbrot set to an arbitrary precision within the limits of the computational power and memory available.

      Many problems are more practical to "solve" by brute force, and by bending the rules - you might not always bother continuing a chain of calculations because it's not practical, and the likelihood of non-termination is so high. Some of them because there are no known optimal solutions, or because you even provably can't determine the optimal solution. Or you may not have any need for a perfect answer - does it affect engineering to not be able to use the exact value for PI? No, in fact in most cases you have no practical need to know it to more decimal places than anyone of us can remember without stupid memory games.

      Brute force is useful because a lot of the time it will give you correct enough results cheaper and faster than the alternatives. Pi for instance might have been mathematically intruiging for centuries, but for all practical purposes an exact enough "solution" was found centuries ago.

      To use your auto repair analogy: I couldn't care less if the technician knows what was wrong or why as long as he fixes it within a reasonable time at a reasonable cost - if that means using a computer diagnostics system that tells him what to do even though he doesn't understand it, then fine. The only thing that matters to me is whether the result is cheap enough, fast enough and safe enough (in other words I WOULD care if the diagnostics system was less likely to catch an impending brake failure than what an experienced mechanic would be).

      Analysis is useful when it teaches us something useful, not as a goal in itself. Of course that what is useful will depend on your goal.

      Besides, often brute force will be the basis for analytical work. It servers several purposes: It provides a benchmark for performance - if your "elegant" solution is slower or not as accurate than a brute force approach it is often pointless, or at the very least useless for a practical implementation. It provides a verification method - often it is much easier to verify the correctness of the brute force approach, as you rely on simple rules, and you can compare the output of the brute force solution to potential analytical solution to get a quick benchmark for how likely it is that the potential analytical solution is correct (and hence whether you want to spend time trying to prove that it is). It demonstrates feasability - if you can whip up a "quick and dirty" brute force solution to a problem the results that often gives you an intuitive insight into whether you are likely to get anywhere with a specific approach to an analytical solution.

      For the worms problem, for instance, the brute force visulisation seem to indicate that a certain set of worms will never terminate. Without the brute force approach, someone might have spent years trying to provide a proof of whether or not they terminate based on the generic ruleset. With the brute force data, the burden of proof is much smaller: You can attack the specific behaviour the seemingly non-terminating worms enter into and attempt to prove that they can't break out of the specific patterns.

      Once you get there, it's quite possible that you'll be able to generalize that proof to find an elegant proof for the entire problem with significantly less effort.

  12. So What! by l810c · · Score: 1
    I could draw better than that.

    Ummm, nevermind...

  13. Re:Who...... by Anonymous Coward · · Score: 1, Insightful

    Who cares? Anybody who wants to be even further discouraged that all the low-hanging fruit in mathematics was plucked a hundred years ago, and that the possibility of finishing grad school in mathematics is diminishing to zero. If you want to teach college mathematics, you have to first somehow produce some sort of results leading to a Ph.D. It's not like you just "go to school" and take classes and finish according to some well-defined plan, the way high school or undergrad college works. You are expected to find some interesting and new idea. Which is so difficult in the field of mathematics anymore that it's totally depressing.

  14. There's an executable... by NortWind · · Score: 1

    Here's an executable for Linux that draws worm tracks. Also some animated GIF's of the trail being drawn.

    1. Re:There's an executable... by NortWind · · Score: 1

      Darn, I thought there'd be no need to preview! The executable link.

    2. Re:There's an executable... by spitzak · · Score: 1

      ./worm_draw: error while loading shared libraries: libcxa.so.3: cannot open shared object file: No such file or directory

    3. Re:There's an executable... by djohnsto · · Score: 1

      Looks like he use icc version 6 to compile. This version of the Intel compiler had it's own libc that it linked to dynamically by default. Version 7 fixed that (switched to glibc, uses statically linked c++ libs). If you can find an install of the version 6 compiler it should work.

      --
      Dan
    4. Re:There's an executable... by NortWind · · Score: 1

      I'm having that problem too! I found the library at this site. I unpacked it, and put it in the directory with the worm draw executable, but it still can't find it. I am (as you may have guessed) a clueless newbie on Linux. I set execute priviledges on the library and the executable.

    5. Re:There's an executable... by spitzak · · Score: 1

      Set the environment varialbe LD_LIBRARY_PATH to the directory the library is in.

      In bash this is "export LD_LIBRARY_PATH /foo/bar"

    6. Re:There's an executable... by NortWind · · Score: 1

      So at the command prompt, should I put in this... export LD_LIBRARY_PATH=/home/rjnorton/games/worms (I did "export -h" for the format.) Will this wipe out any existing library path?

    7. Re:There's an executable... by cyt0plas · · Score: 1

      I don't think it does, but the environment variables are reset at logon, so it really doesn't matter. You could also probably put the library in /lib, and run ldconfig.

      --
      Contact Me (got tired of viruses emailing me).
    8. Re:There's an executable... by ACorvus · · Score: 1

      export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/where/your/lib/i s
      ldconfig

      extra text here for lameness filter!

      --
      -- Sig Sig Sputnik
    9. Re:There's an executable... by NortWind · · Score: 1

      Thanks to all! I can get it to run ( ** enough to get the help info anyway) now.

    10. Re:There's an executable... by Annamite · · Score: 1

      This whole step-thread is the exact reason why Linux is not and will not the operating system for the regular "normal" people out there. The only people who understand this whole particular thread are obviously geeks. :-)

    11. Re:There's an executable... by NortWind · · Score: 1

      I think Linux works fine for non-geeks. My installations was super-easy, just feeding the CD's through. And all the installation using RPM files were just point and click, as easy as any Windows setup program. The thing that Linux brings is that it lets you get under the hood and tinker, which I want to learn how to do. I suppose Windows has RegEdit, but that is just as geeky and even more dangerous that export + ldconfig.

    12. Re:There's an executable... by spitzak · · Score: 1

      Nonsense. This is exactly the same problem you would have if somebody sent you a Windows .exe that requires a .dll and they did not send you the .dll. In fact we screwed up the first release of our own Windows software for exactly the same reason, we neglected to include the .dll files the Intel compiler required.

  15. Martin Gardner is my hero by Shimmer · · Score: 4, Interesting

    I devoured his columns as a boy. His simple, clear writing style made it easy to understand very sophisticated concepts. Today, I aspire to write like he did.

    He is getting on in years and it's been awhile since I've seen anything new from him (either on math or junk science, his other favorite topic). His collection, The Night is Large is a great overview of his work.

    Anway, it's a pleasure just to see his name and know that people are still pursuing the topics he wrote about.

    -- Brian

    --
    The most rabid believers in American Exceptionalism are the exact same people whose policies are destroying it.
  16. Whoa - I went to school with him by AssFace · · Score: 1

    Ben and I were on the track and XC team together at Williams. He was a year ahead of me. I knew that he worked at Intel, but hadn't kept in touch.

    --

    There are some odd things afoot now, in the Villa Straylight.
    1. Re:Whoa - I went to school with him by Baggio · · Score: 1

      That's not such a tough run... it's all down hill. :O

      --
      Time flies like an arrow;
      Fruit flies like a bananna
  17. Run this on Big Mac by Qrlx · · Score: 3, Funny

    from the article Currently my grid is about 1.57 million points on a side

    If he's saying that the 2 worms hit the end of the 1.57million^2 grid, in a non-repeating pattern, that's pretty neato. We must know where it ends! Put it on Big Mac, make the grid bigger, and call it iWorms.

  18. Multi-player worms game; anyone remember? by khym · · Score: 1

    A long time ago, I had a mult-player game based on this: each player would have a different colored worm, and if a worm encountered a configuration it hadn't seen before, it would prompt it's player for what to do in that situation; the game wrapped top/bottom and left/right (set on a torus), so it couldn't go on forever. It was sort of psychedelic watching the different colors spread and writhe over the screen,, and interesting to see how your rules interacted with the rules of the other players' worms. Really fun, for such a simple game.

    --
    Give a man a fire, and he'll be warm for a day, but set him on fire, and he'll be warm for the rest of his life.
    1. Re:Multi-player worms game; anyone remember? by Trinn · · Score: 1

      If you happen to have the code, I'd like to see it, I'm curious. Perhaps you can e-mail it? This sounds like it could be developed into the kind of strategy game a friend of mine always is hoping to find.

    2. Re:Multi-player worms game; anyone remember? by anusbagger · · Score: 1

      You might be talking about skweedunques, programmed by alex healy, who is crazy smart.

  19. I wonder... by 96804896 · · Score: 1

    I wonder what these worm trail pictures tell us about the Pentium 4 design. Can anyone identify the 64 bit extensions?

  20. Re:Next Task, Chess by FrankoBoy · · Score: 1

    Well about computers and chess, you could start with this discussion here on /. two weeks ago...

    --

    United States of America, good ol' backers of world peace.
  21. Re:MOD PARENT? by NortWind · · Score: 1

    It's not a virus, it's a worm, you insensitive clod!

  22. Comment removed by account_deleted · · Score: 1

    Comment removed based on user account deletion

  23. Re:Who...... by johnny0101 · · Score: 1

    Mathematics is constantly being created to describe new (or old!) problems being run into by researchers. More mathematics has been developed in the past 100 years than in the history of mankind, and more continues to be discovered... Anyone with the insight and genius can discover something new (and i certainly do NOT claim to be one of these people). That's the way it's always been and the way it always will be. And at the risk of flaming (it's not intended to be!) you probably shouldn't be allowed to hold a PhD in math unless you truly have some insight that nobody else has.

    --

    ----
    In Soviet Russia, the overlords welcome you!
  24. [OT] Re:Multi-player worms game; anyone remember? by Luyseyal · · Score: 1

    the game wrapped top/bottom and left/right (set on a torus)

    Isn't that just a sphere? What makes it a torus?

    -l

    --
    Help cure AIDS, cancer, and more. Donate your unused computer time to worldcommunitygrid.org. Join Team Slashdot!
  25. Evolution is not brute force... by Anonymous Coward · · Score: 3, Interesting

    Brute force is taking all the possible combinations (e.g. all the base pair combinations in DNA) and test them *once*.

    Evolution takes a small sample (the current instances of gene combinations, i.e. the current generation) and creates another small pool (the next generation) depending on a selection algorithm (survival of the fittest). Most combinations are never ever tested.

    And unlike a traditional brute force approach, the same gene combination may be tested many times (in theory at least), and the selection is not deterministic (that is, the "best" individual can e.g. die by chance).

    Another thing, brute force may only find the best selection if there is one such combination of genes. Contrary to that, it is likely that there'll be specializations in the gene pool (e.g. at some point, many species specialized into male and female forms, some into worker/queen etc.)

    Kjella (have moderated thread, so ACing)

    1. Re:Evolution is not brute force... by ejito · · Score: 2, Interesting
      Brute force is taking all the possible combinations (e.g. all the base pair combinations in DNA) and test them *once*.
      Brute forcing doesn't have to test all cases. It tests to find answers to cases, not EVERYTHING. When you find an answer, you stop the testing.

      Plus your idea that mother nature repeats test cases is false. Every human generation is unique. Even when twins are born, the twins will reproduce with two different people creating another expansive tree. Even then, twins have subtle mutations in their DNA, along with small differences in societal status, evironiment. No matter what you'll never end up with the same test case again.
      Most combinations are never ever tested.
      That's because the combinations are infinite. Just because a tree is infinite does NOT mean we can't brute force to find the answers we are looking for.

      Mother nature (math) has brute forced her way to us. It was testing for cases of survival. Whether or not we are superior is not the point of survival. We survived, therefore we are the best case so far.

      If an intelligent life form made out of steel can't survive, than obviously it has failed the test case, even if it better than us by our standards.
      and the selection is not deterministic (that is, the "best" individual can e.g. die by chance)
      Yeah, so sh* happens because we think it's sh*. If a genius and healthy man dies from getting hit with an SUV, it might seem unfair to us. In the society we live in, the "world" is filled with cars -- whether one can survive within that world becomes a new test case.

      There can also be several "answers", which lies truth to a degree which our human mind will accept.
    2. Re:Evolution is not brute force... by Peyna · · Score: 1

      If only Mother nature had used better heuristics.

      --
      What?
  26. Re:John Conway and the complexity of life by frovingslosh · · Score: 1
    Life is very similar to "worms" but is actually much simpler.

    Yes it's the same Conway. And Life is certainly NOT much simpler than worms. if anything it is much more complex. Both start with a simple set of rules that lead to complex patterns, but with worms there is only a point at any one time, and the patterns are only in it's past history and the changes it has made to it's landscape, a landscape that is consumed. But life and it's variants have multiple points of dynamic change each move (generation). It can show motion in multiple locations and multiple directions at once. It shows beauty and patterns both in it's history and in it's current generation. Conway's game of life, in it's many variations, is actually more complex than worms.

    Worms does look more novel, particularly in that it is usually played on a triangular or hexagon grid work, while life is usually played on a square cellular structure. By life is not limited to a 2-d squale cellular structure and more than wormes is limited to a hexagon based structure. Life could certainly be played on a hexagon cell board, as well as many other cell arangements. I expect the main reason life is predominately seen on a square cell arangement is simply because Y by Y arrays lend themself very well to playing life in software, and it is still a complex game on a simple square cellular universe.

    --
    I'm an American. I love this country and the freedoms that we used to have.
  27. Fractals by KingRob · · Score: 1

    Has anyone noticed how similar these worms look to fractal pictures? julia sets worms example #57

  28. Encryption...? by Gwala · · Score: 4, Interesting

    Strange Idea, but, what about using this in encryption for pseudo-random number generation?

    It's obviously simple to implement, but requires exponential processor/mem usage to generate each successive generation of pattern's. Would this be effective? would the reduced keyspace be better or worse than the computational requirements?

    --
    #!/bin/csh cat $0
  29. Could a mathematician please explain... by salimma · · Score: 1
    ... how the rules are supposed to be followed? I've read Ed Pegg's page as well as the AccessV page, but when working through the patterns I get stuck at '2 5 1 0'; instead of getting a 180 degree rotation of '2 1 0 4' I get an infinite pattern.

    I was trying to take the first possible move available (e.g. for 2 1 0 4, try 2, then 1, then 0, then 4) but it's apparently not what I should be doing...

    Thanks!

    --
    Michel
    Fedora Project Contribut
  30. Remember? Hell.. by Kwil · · Score: 1

    ..I still play.

    http://www.netives.com/Games/Wormz/index.njsp

    --

    That Jesus Christ guy is getting some terrible lag... it took him 3 days to respawn! -NJ CoolBreeze

  31. The graphics... by Slime-dogg · · Score: 1

    Yeah, it's a bitching about the graphics of the page.

    Would if have been too much work to put separators in the first graphic? The thing is confusing enough, but made more so by leading the person to think that it is one long pattern with six different worms doing their own thing.

    --
    You need to restart your computer. Hold down the Power button for several seconds or press the Restart button.
  32. Hofstadter for me by Angostura · · Score: 1

    But, Gardner as back-up. :-)

  33. STUPID FUCKING MODS by Anonymous Coward · · Score: 1, Informative

    Next time, try reading the fucking thing.

    Idiots. Asshats. The lot of you.

  34. Re:Next Task, Chess by grosa · · Score: 1

    In short, no. There are more outcomes of chess then there are particles in the known universe. see the other reply for the previous discussion on chess.

  35. Re:THE ANSWER IS......FORTY TWO by Patrik_AKA_RedX · · Score: 1
    perhaps it is...six times nine?
    Nope. 6 * 9 = 54. That's The question for a differend universe.
  36. Oh no by JWhiton · · Score: 2, Funny

    Oh great, another worm? Where do I get the patch from this time?

  37. Re:Who...... by Knights+who+say+'INT · · Score: 1
    Switch to economics. Plenty of low-hanging fruit there, particularly for people with a proper mathematical background.

    You might also get rich in the process. Remember all the voodoo finance tricks taught in business schools were invented/discovered by economists.

    Did I mention we just rule?

  38. Rules Explanation by mattr · · Score: 1

    This is great but it took a long time to figure out the rules since the description is so horrible. Well I got this far so good luck!

    For 104015 as drawn here is the list of decisions. Basically it seems that every time the worm comes across a point with an eaten segment attached to it, the worm takes the next rule as a new decision, then draws a segment, and then goes back to the first rule in the list (which makes it try to start drawing a hexagon again). However I have to say that Pegg's coloring is rather arbitrary, that lone green segment in the middle stumped me for a while! Also the way decisions are made is not intuitive.

    111111 black hexagon
    Hit hexagon starting point, pick rule #2 which is a "0".
    0 go straight one segment in red.
    Go back to start of program, now use rule #1:
    111 draw three more red segments using that rule.
    Hit the black hexagon again, pick rule #3 (a "4") unclear yet whether it is picked because it is next in order or because the rules #1 and #2 can't be used. But considering next decision, I believe it is because it is next in order:
    4 turn two hours to left and draw first blue segment. Then go back to beginning of program.
    1111 draw four more blue segments until black hexagon is hit again.
    Hit hexagon, pick rule #4 (a "0").
    0 draw first yellow segment straight ahead. Then go back to beginning of program
    1 draw second yellow segment.
    Hit a vertex of the black hexagon, but we can crash through for some reason. So we keep drawing segments with rule #1 which should be in yellow but is green in the drawing:
    11 draw two more segments
    Hit the blue hexagon so pick rule #6 (a "5").
    5 turn two hours to left and draw another green segment. Then go back to beginning of program with rule #1:
    1111 draw more green segments
    Hit blue hexagon again. Rule #1 doesn't do the job so rule #2 (a "0"):
    0 go straight ahead drawing a single green segment. Then back to beginning of program with rule #1:
    1 turn right and draw a single green segment.
    Hit black hexagon, so pick next rule. All the rules are useless but the last rule #6 (a "5"):
    5 turn left and draw a single green segment. Then go back to beginning of program and rule #1:
    1 turn right and draw a single green segment.
    Now we hit the black and red hexagons so another decision is to be made and we are into magenta which I won't follow.

    It still seems wierd how decisions are made and maybe following magenta for yourself will tell you how the recursion is supposed to be done. Personally I would rather see some pseudo code since it is difficult to tell which of the two "0" rules is being chosen.

  39. Moderators are incorrect by Pentagram · · Score: 2, Insightful

    Evolution is not brute-force. Evolution is a learning method in that each new generation is based on the results of the previous generation.

    Your nucleic DNA contains approx 3*10^9 bases. That's 4^(3 billion) permutations. Just how long do you think it would take if you worked through AAAA...AAAA , AAAA...AAAT etc. before you came up with something as workable as the human genome? Same deal with a random walk.

  40. Re:Who...... by johnny0101 · · Score: 1

    Switch to economics.

    Actually, i was seriously considering economics but i guess i was suckered into computer engineering cuz i thought i liked it ;)
    I wanted to double major but now i just want out of school!
    maybe i'll go back and do an econ degree... it's always been interesting to me.

    --

    ----
    In Soviet Russia, the overlords welcome you!
  41. does this take other things into account? by simetra · · Score: 1

    Like... the pitter-patter of rain, moisture in the soil, ground vibrations cause by other things, like nearby animals, fishermen, etc?

    --

    "Would it kill you to put down the toilet seat?" -- Maya Angelou
  42. Looks pretty simple to me by laing · · Score: 1

    The Game of Life was invented by John Conway (as you might have gathered). The game is played on a field of cells, each of which has eight neighbors (adjacent cells). A cell is either occupied (by an organism) or not. The rules for deriving a generation from the previous one are these:
    Death: If an occupied cell has 0, 1, 4, 5, 6, 7, or 8 occupied neighbors, the organism dies (0, 1: of loneliness; 4 thru 8: of overcrowding).
    Survival: If an occupied cell has two or three neighbors, the organism survives to the next generation.
    Birth: If an unoccupied cell has three occupied neighbors, it becomes occupied.

    Note that there's no food involved (as there is in "worms"). Also note that many more implementations of "life" exist, and have existed for much longer than "worms". This is due to the fact that it's a simpler simulation to code. I remember running life 25 years ago on CP/M platforms.

    P.S. Why in the world was my original post modded down as redundant? There were no other posts, and no information in the article that made this association.
    --
    This space for rent.

    1. Re:Looks pretty simple to me by Theodore+Logan · · Score: 1

      I don't know much about these worms, having never heard of them before, but you seem to be under the impression that just because the rules of Life are simpler than the rules these worms adhere by Life's behavior must also be less complex, or more generally, that a more complex ruleset necessarily results in more complex behavior. This is not so, and in fact demonstrating that this is not so was Conway's prime motivation for creating Life in the first place.

      I don't know why you feel compelled to reiterate the rules of Life and who invented them when it is obvious that the poster you replied to already knows all this. As for why you were moderated redundant, I can only conjecture that it was because John Conway is very famous and that everybody's sick of hearing about Life in every article that mentions his name.

      --

      "If you think education is expensive, try ignorance" - Derek Bok

  43. Oh yeah, that screensaver by WebMasterJoe · · Score: 1

    I always wondered what the screensaver had to do with worms. Now I know - it's a simulation of worms eating food in 1969, or something. I guess I still don't know. Damn you computer scientists, and your weird algorithms!

    --
    I really hate signatures, but go to my website.
    1. Re:Oh yeah, that screensaver by Avatar889 · · Score: 1

      Any idea where I could get that screensaver?

      --
      Nullum magnum ingenium sine mixtura dementia (There is no great genius without a mixture of madness) - Aristotle
    2. Re:Oh yeah, that screensaver by WebMasterJoe · · Score: 1

      I'm not sure who makes it, but every linux distro (at least every one since RH 5.2) I've used seems to have that screensaver included. I believe it's in Gnome, but it might be KDE. All I know is I've never seen it in Windows.

      --
      I really hate signatures, but go to my website.
  44. uhh by TotallyUseless · · Score: 1

    what?

    --

    Time for some tasty Shiner Bock!
  45. Moo by Chacham · · Score: 1

    Martin Garnder is rather intelligent. Yet, he is also a pompous fool. If you read his books, his arrogance is astounding, and only what he believes is sensical. This shows up in some of his preferatory remarks and explanations. But, he is good at some things. While the Aha! books are mildly reprehensible (for the aforementioned reasons) their thought-provoking comments outweigh them many times over.

    --
    Have you read my journal today?
  46. Re:Modstalker reply: by Theodore+Logan · · Score: 1

    Thank you for replying in such honesty.

    It's nothing really personal. I get mod points, and when they are about to expire, any I haven't used go to the first red dots I see. I just figure if you can make someone a foe for no apparent reason, than you can be modded redundant for no apparent reason.

    When I made you a foe, whoever you are, I had a reason. I can't tell you which reason, since you refuse to say who you are. Most likely, it was just because I had found a lot of your comments uninteresting and wanted to save myself some time by not reading any of them in the future (which is all that is achieved by making someone a foe). Although you might have angered me, this probably isn't the case. And even if it were I fail to see why it is that you should seek vengeance because of this.

    Do you consider it reasonable to try to penalize me merely because I am not interested in reading what you write? Don't you see that the situation is asymmetrical? I judge who you are from what you say, which is fine. You, on the other hand, judge what I say from who I am, which is fallicious. Furthermore, by moderating me down without a clear reason you deprive me of my ability to make myself heard, and you deprive the Slashdot community of my comments. By making you a foe, I deprive noone but myself of anything.

    The little red dots insure that I don't let my precious mod points expire.

    Maybe you should ask yourself if letting them expire is really worse than to use them irrationally? Is it not better not to moderate than to moderate in a way that ruins what the moderation system seeks to accomplish? Finally, don't you see the irony in that by desperately wanting to use all mod points you will, by meta-moderation, eventually remove yourself from the pool of users who are elegible for moderator status? M2 was created to prevent systematic abuse like yours, and it does work.

    --

    "If you think education is expensive, try ignorance" - Derek Bok

  47. Re:Modstalker reply: by Theodore+Logan · · Score: 1

    Hello again.

    Making someone a foe also announces to all of the users in your Friends list that I am some kind of dickhead. Well, maybe I am, but who the hell are you to say so?

    No, it doesn't. You put to much weight on the word "foe." It doesn't literally mean that you are my foe. It means that I am not interested in what you write. And as to "who am I to say so," I say so because I have read what you write and didn't like it. It is quite obvious, really.

    You judge me for what I said, once. Or twice on the outside.

    Well, you never said who you are, so how could I know this? If what you say is true, you are most certainly a very rare breed. Either you said something outrageously stupid, or I just had a bad day, but most people of my foe-list have a long history of comments unworthy of attention.

    This comment of yours further suggests that you are newcomer to this community. I have been for more than five years, almost since the beginning. Might it not be a good idea for you to try see how things work around here for a year or so before going on personal crusades?

    You give me no recourse to ammend or reverse my position, you irrevokeably label me as unworthy to all who would befriend you.

    It is not I who give you no recourse for amendment, it is Slashcode. I'm sorry that the system is built this way, but it's most certainly not my fault. And, again, those who befriend me will, if rational, judge you from what you say and not from the color of the dot next to your name. I, for one, have never ever chosen not to read a comment because the person who wrote it was "foe of a friend," and in all honesty I will admit to not even knowing what that symbol looks like. Most people who don't take moderation too seriously (in other words, the vast majority) probably reason the same way.

    And actions have consequences in life, and consequences are seldom symmetrical.

    You cannot derive "ought" from "is."

    First of all, it's pretty self-important of you to think what you have to say is all that important.

    No, it isn't. I regard myself as a random poster with no particular insight into anything, and I regard you as a random moderator. What would happen if every random moderator would moderate any random poster on the grounds that you moderate me? The system would cease to work, that's what. Because occasionally, although, as you say, in all likelyhood not very often, I will write something that the community will want to read, and then you will deprive them of that. See what your actions mean in a larger context, and it will become apparent how they deprive the community of value.

    I really do read your posts before modding them to oblivion.

    If this is true, it makes a large difference. It also, to some extent, contradicts a lot of what you've said so far. Tell me honestly, were the five posts that you moderated redundant in a row really so?

    Do most people who know you well describe you as conceited to a fault? Or do you only come off that way in your posts?

    I don't understand what you're getting at. Please elaborate.

    Would you believe the majority of those were M2'ed as Fair? Because with the exeception of one, they were. So Actually I'm getting positive reinforcement. And Yes, That's why I chose "Redundant'

    Yes, I believe you. I had forgotten that you chose the "redundant" appellation. Most M2ers don't have time to check the context and see if posts are really only reiterating already expressed opinions or facts. But does not your admitting to trying to cheat the system by systematically choosing the "redundant" appellation mean that you either have to regard the system as faulty or that you are actively trying not to serve its users only because you have a personal axe to grind?

    Again, I thank you for replying, as I must admit that you have no real reason to, except to please me and perhaps yourself. Still, I am at a complete

    --

    "If you think education is expensive, try ignorance" - Derek Bok