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

6 of 173 comments (clear)

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

    3. 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.
  2. 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.

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