Slashdot Mirror
Paterson's Worms Solved by Number-Crunching
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."
Did somebody say worms?
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?
find / -name "*.sig" | xargs rm
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
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
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)
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.
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.
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.
who's name is also mentioned in the article, may be the same John Conway who invented "life". Life is very similar to "worms" but is actually much simpler. It's available on just about every version of X windows as a screensaver.
...is what will really put brute force processing to shame as we know it.
Life is not for the lazy.
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.
Ummm, nevermind...
Who cares? Anybody who wants to be even further discouraged that all the low-hanging fruit in mathematics was plucked a hundred years ago, and that the possibility of finishing grad school in mathematics is diminishing to zero. If you want to teach college mathematics, you have to first somehow produce some sort of results leading to a Ph.D. It's not like you just "go to school" and take classes and finish according to some well-defined plan, the way high school or undergrad college works. You are expected to find some interesting and new idea. Which is so difficult in the field of mathematics anymore that it's totally depressing.
Obviously, at least one person cares or it would not be (Slashdot) news. I for one find it somewhat interesting.
Here's an executable for Linux that draws worm tracks. Also some animated GIF's of the trail being drawn.
I for one welcome our new interesting overlords.
I've always wondered if computers will soon be unbeatable at chess, simply because they've calculated all possible outcomes of the game and know how to always win or at least force a draw (kind of like finding out that you can always force a "cat" at tic-tac-toe). So do you think the player who moves first would always win or could the 2nd player always force a draw?
Link is a VIRUS! It will hack your Linux!
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.
And a hundred years before that they were just falling on people's heads. Lucky bastards!
Funniest story I've read in a while, thanks.
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.
There are some odd things afoot now, in the Villa Straylight.
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. Really fun, for such a simple game.
Give a man a fire, and he'll be warm for a day, but set him on fire, and he'll be warm for the rest of his life.
I wonder what these worm trail pictures tell us about the Pentium 4 design. Can anyone identify the 64 bit extensions?
It's not a virus, it's a worm, you insensitive clod!
Comment removed based on user account deletion
Mathematics is constantly being created to describe new (or old!) problems being run into by researchers. More mathematics has been developed in the past 100 years than in the history of mankind, and more continues to be discovered... Anyone with the insight and genius can discover something new (and i certainly do NOT claim to be one of these people). That's the way it's always been and the way it always will be. And at the risk of flaming (it's not intended to be!) you probably shouldn't be allowed to hold a PhD in math unless you truly have some insight that nobody else has.
----
In Soviet Russia, the overlords welcome you!
i can't stop laughing
but we must understand the question! perhaps it is...six times nine?
Do you or your partner snore? - Visit www.snoring.com.au
Isn't that just a sphere? What makes it a torus?
-l
Help cure AIDS, cancer, and more. Donate your unused computer time to worldcommunitygrid.org. Join Team Slashdot!
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)
Yes it's the same Conway. And Life is certainly NOT much simpler than worms. if anything it is much more complex. Both start with a simple set of rules that lead to complex patterns, but with worms there is only a point at any one time, and the patterns are only in it's past history and the changes it has made to it's landscape, a landscape that is consumed. But life and it's variants have multiple points of dynamic change each move (generation). It can show motion in multiple locations and multiple directions at once. It shows beauty and patterns both in it's history and in it's current generation. Conway's game of life, in it's many variations, is actually more complex than worms.
Worms does look more novel, particularly in that it is usually played on a triangular or hexagon grid work, while life is usually played on a square cellular structure. By life is not limited to a 2-d squale cellular structure and more than wormes is limited to a hexagon based structure. Life could certainly be played on a hexagon cell board, as well as many other cell arangements. I expect the main reason life is predominately seen on a square cell arangement is simply because Y by Y arrays lend themself very well to playing life in software, and it is still a complex game on a simple square cellular universe.
I'm an American. I love this country and the freedoms that we used to have.
Has anyone noticed how similar these worms look to fractal pictures? julia sets worms example #57
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
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!
Michel
Fedora Project Contribut
..I still play.
http://www.netives.com/Games/Wormz/index.njsp
That Jesus Christ guy is getting some terrible lag... it took him 3 days to respawn! -NJ CoolBreeze
Take a flat map of the world, and imagine wrapping it around a sphere. Notice that if you move off the top of the map (say above Canada somewhere) you would fly back onto the map above Russia.
On the other hand, if you wrap that same map of the world around a donut, you'll see that flying north of Canada will bring you back over Antarctica. (The north edge of the flat map and the south end of the flat map will actually meet on the donut).
Maybe then you should take it easy on the drugs, you waste-of-space burnout stoner asshole. Get a life and get a job, and get the fuck away from the god-damn computer you lazy worthless bastard.
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.
You need to restart your computer. Hold down the Power button for several seconds or press the Restart button.
But, Gardner as back-up. :-)
I read through a couple sentences and then my eyes glazed over and then I blanked out and scrolled down and I heard this thought playing through my brain and unglazed my eyes and stared up at the ceiling and I moo-ed.
But it wasn't a moo. It was more of a double sylable sort of thing.. sort of goes like this:
booooooo riiinnggggg
Next time, try reading the fucking thing.
Idiots. Asshats. The lot of you.
Imagine this: Rectangle.
Top and bottom of rectangle wrap around i.e., are touching. So it's a pipe.
Left and right of rectangle wrap around i.e., are touching. Fold it again so the ends of the pipe touch.
Mmm... quasi-infinite donut...
Oh great, another worm? Where do I get the patch from this time?
You might also get rich in the process. Remember all the voodoo finance tricks taught in business schools were invented/discovered by economists.
Did I mention we just rule?
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 rather arbitrary, that lone green segment in the middle stumped me for a while! Also the way decisions are made is not intuitive.
111111 black hexagon
Hit hexagon starting point, pick rule #2 which is a "0".
0 go straight one segment in red.
Go back to start of program, now use rule #1:
111 draw three more red segments using that rule.
Hit the black hexagon again, pick rule #3 (a "4") unclear yet whether it is picked because it is next in order or because the rules #1 and #2 can't be used. But considering next decision, I believe it is because it is next in order:
4 turn two hours to left and draw first blue segment. Then go back to beginning of program.
1111 draw four more blue segments until black hexagon is hit again.
Hit hexagon, pick rule #4 (a "0").
0 draw first yellow segment straight ahead. Then go back to beginning of program
1 draw second yellow segment.
Hit a vertex of the black hexagon, but we can crash through for some reason. So we keep drawing segments with rule #1 which should be in yellow but is green in the drawing:
11 draw two more segments
Hit the blue hexagon so pick rule #6 (a "5").
5 turn two hours to left and draw another green segment. Then go back to beginning of program with rule #1:
1111 draw more green segments
Hit blue hexagon again. Rule #1 doesn't do the job so rule #2 (a "0"):
0 go straight ahead drawing a single green segment. Then back to beginning of program with rule #1:
1 turn right and draw a single green segment.
Hit black hexagon, so pick next rule. All the rules are useless but the last rule #6 (a "5"):
5 turn left and draw a single green segment. Then go back to beginning of program and rule #1:
1 turn right and draw a single green segment.
Now we hit the black and red hexagons so another decision is to be made and we are into magenta which I won't follow.
It still seems wierd how decisions are made and maybe following magenta for yourself will tell you how the recursion is supposed to be done. Personally I would rather see some pseudo code since it is difficult to tell which of the two "0" rules is being chosen.
open4free
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.
Cellular automata are a poor basis for encryption. They may have chaotic behavior, but it is decidedly non-random and often locally very predictable. Using a poorly-understood cellular automata for encryption would not only perform very poorly but would also provide much poorer security than better-understood algorithms designed for this purpose.
Switch to economics.
;)
Actually, i was seriously considering economics but i guess i was suckered into computer engineering cuz i thought i liked it
I wanted to double major but now i just want out of school!
maybe i'll go back and do an econ degree... it's always been interesting to me.
----
In Soviet Russia, the overlords welcome you!
Like... the pitter-patter of rain, moisture in the soil, ground vibrations cause by other things, like nearby animals, fishermen, etc?
"Would it kill you to put down the toilet seat?" -- Maya Angelou
The Game of Life was invented by John Conway (as you might have gathered). The game is played on a field of cells, each of which has eight neighbors (adjacent cells). A cell is either occupied (by an organism) or not. The rules for deriving a generation from the previous one are these:
Death: If an occupied cell has 0, 1, 4, 5, 6, 7, or 8 occupied neighbors, the organism dies (0, 1: of loneliness; 4 thru 8: of overcrowding).
Survival: If an occupied cell has two or three neighbors, the organism survives to the next generation.
Birth: If an unoccupied cell has three occupied neighbors, it becomes occupied.
Note that there's no food involved (as there is in "worms"). Also note that many more implementations of "life" exist, and have existed for much longer than "worms". This is due to the fact that it's a simpler simulation to code. I remember running life 25 years ago on CP/M platforms.
P.S. Why in the world was my original post modded down as redundant? There were no other posts, and no information in the article that made this association.
--
This space for rent.
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!
I really hate signatures, but go to my website.
what?
Time for some tasty Shiner Bock!
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.
Have you read my journal today?
Hi, I am the person who has been modding you redundant, well not this post, because I'm making the comment, but you know when.
It's nothing really personal. I get mod points, and when they are about to expire, any I haven't used go to the first red dots I see. I just figure if you can make someone a foe for no apparent reason, than you can be modded redundant for no apparent reason. I have no Idea what I did to earn your animosity, so I am insuring I earn it after the fact.
The little red dots insure that I don't let my precious mod points expire.