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

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

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

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

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