Follow Slashdot stories on Twitter

 


Forgot your password?
Close
typodupeerror
×
Programming Education IT Technology

Paterson's Worms Solved by Number-Crunching 173

Posted by michael 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."
This discussion has been archived. No new comments can be posted.

Paterson's Worms Solved by Number-Crunching More

Paterson's Worms Solved by Number-Crunching

Comments Filter:

  • Worms? (Score:4, Interesting)

    by No_Weak_Heart ( 444982 ) on Friday October 24, 2003 @09:37PM (#7306280)

    Did somebody say worms [wormsinsand.org]?

  • Chaffin solves Patterson's Worms... (Score:2, Funny)

    by Anonymous Coward
    Sounds painful...
  • ...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?

  • trippy (Score:5, Funny)

    by cr@ckwhore ( 165454 ) on Friday October 24, 2003 @09:39PM (#7306295) Homepage
    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.

    • 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

  • Or... (Score:5, Funny)

    by TheSpoom ( 715771 ) * <slashdot@ubermAA ... inus threevowels> on Friday October 24, 2003 @09:42PM (#7306315) Homepage Journal
    Another great background for that monitor that can do 30000x40000.

  • Worms and computers (Score:1, Informative)

    by Anonymous Coward
    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)

  • It is my belief that... (Score:4, Insightful)

    by cliffy2000 ( 185461 ) on Friday October 24, 2003 @09:52PM (#7306353) Journal
    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.
    • Comment removed based on user account deletion

    • Re:It is my belief that... (Score:5, Insightful)

      by dekashizl ( 663505 ) on Friday October 24, 2003 @10:09PM (#7306418) Journal
      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.

      • Re:It is my belief that... (Score:5, Interesting)

        by DarkSarin ( 651985 ) on Friday October 24, 2003 @10:28PM (#7306483) Homepage Journal
        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.

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

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

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

          Ther

    • Re:It is my belief that... (Score:4, Interesting)

      by lawpoop ( 604919 ) on Friday October 24, 2003 @10:12PM (#7306434) Homepage Journal
      Brute force, aka trial-and-error, is what drives evolution. Brute force created the human brain, your mind, and thought.

      • Evolution is not brute force... (Score:3, Interesting)

        by Anonymous Coward
        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 sele

        • 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

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

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

    • 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 [google.com].

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

    • 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 [wolfram.com] 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 [wolfram.com].

    • This is an emergent phenomenon, like The Game of Life [bitstorm.org] and Langton's Ant [libero.it].

      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 no

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

  • Other sites (Score:5, Informative)

    by goddess_warshipr ( 712258 ) on Friday October 24, 2003 @09:56PM (#7306365)
    There are more pictures at Benjamin Chaffin's page. [williams.edu]
    There is more information on the games and rules at Sven's page [accessv.com], that includes a comparison of Chaffin's notation to Gardner's and a comparison of Worms to the Game of Life. [math.com]

  • Brute Force (Score:3, Insightful)

    by Anonymous Coward on Friday October 24, 2003 @10:03PM (#7306391)
    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.
    • 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.
    • 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.
  • Here's an executable for Linux that draws worm tracks. Also some animated GIF's of the trail being drawn.
    • Darn, I thought there'd be no need to preview! The executable [williams.edu] link.
      • ./worm_draw: error while loading shared libraries: libcxa.so.3: cannot open shared object file: No such file or directory
        • 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.
        • I'm having that problem too! I found the library at this [zetagrid.net] 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.
          • Set the environment varialbe LD_LIBRARY_PATH to the directory the library is in.

            In bash this is "export LD_LIBRARY_PATH /foo/bar"
            • 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?
              • 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.

  • Martin Gardner is my hero (Score:5, Interesting)

    by Shimmer ( 3036 ) on Friday October 24, 2003 @10:50PM (#7306573) Journal
    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
  • 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.

  • Run this on Big Mac (Score:4, Funny)

    by Qrlx ( 258924 ) on Friday October 24, 2003 @11:21PM (#7306649) Homepage Journal
    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.

  • 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.
  • I wonder what these worm trail pictures tell us about the Pentium 4 design. Can anyone identify the 64 bit extensions?
  • Has anyone noticed how similar these worms look to fractal pictures? julia sets worms example #57 [accessv.com]

  • Encryption...? (Score:4, Interesting)

    by Gwala ( 309968 ) <adam AT gwala DOT net> on Saturday October 25, 2003 @02:20AM (#7306981) Homepage
    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?
  • ... how the rules are supposed to be followed? I've read Ed Pegg's page [maa.org] as well as the AccessV page, but when working through the patterns [accessv.com] 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!

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

  • Oh no (Score:3, Funny)

    by JWhiton ( 215050 ) on Saturday October 25, 2003 @08:20AM (#7307759) Homepage
    Oh great, another worm? Where do I get the patch from this time?
  • 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 rath
  • Like... the pitter-patter of rain, moisture in the soil, ground vibrations cause by other things, like nearby animals, fishermen, etc?

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

  • Moo (Score:2)

    by Chacham ( 981 ) *
    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.

Slashdot Top Deals

Life is a game. Money is how we keep score. -- Ted Turner

Close