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

21 of 173 comments (clear)

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

    Did somebody say worms?

  2. Chaffin solves Patterson's Worms... by Anonymous Coward · · Score: 2, Funny

    Sounds painful...

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

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

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

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

  12. 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.
  13. 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
  14. Oh no by JWhiton · · Score: 2, Funny

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

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