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

9 of 173 comments (clear)

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

    Did somebody say worms?

  2. 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
  3. 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
  4. 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 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)
  5. 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.
  6. 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.
  7. 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