[Some questions] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Some questions
(Click here to view the original thread with full colors/images)
Posted by: green_meklar
First, I hope I'm posting in the right forum, and I hope using a screenname isn't too illegal, because so far I've managed to keep my real name off the Internet and I want it to stay that way. I'm a bit of an NKS noob, but I'm interested in the subject and I did a few limited experiments using a TI-83 graphing calculator (I wrote myself a program that can cover all the 256 basic rules, on a wrapping surface) and Microsoft Excel. Now I have a few of questions about it.
First question: I know that a pattern which cannot be the result of any other pattern is called a Garden of Eden pattern. I also know that any cellular automaton with limited width and cell states and no inserted randomness must eventually get stuck in a loop. What I'm wondering is, is there a name for patterns which, although they are not Garden of Eden patterns, eventually lead to a loop which does not include them? Something like 'irreversible'?
Second question: One of the rules I played around with was rule 73 (this one). It seems to me the interactions between bars could be quite interesting if it weren't for those nasty two-pixel-wide pillars that show up all over the place and act as walls. And from what I can tell, all that is necessary to prevent those pillars is to ensure, somehow, that all the lines of solid white or black in the initial generation have an odd number of pixels in them. So, has anyone tried using that kind of initial setup and studied the way those bars interact? If so (and I assume someone must have done it), is there anything interesting about them?
Posted by: Jason Cawley
On question one, they are called transients.
A state transition diagram plots all the possible states in a system (here a CA, with a certain fixed width), with each state pointing to the state that it leads to next.
On such a diagram, the states that eventually revisit each other are called a cycle or sometimes an attractor, and will appear as one or more circles.
The states that fall onto a particular cycle are called its basin of attraction. These appear as multiple "arms" - the transients - directed in to the cycle, sometimes branches that converge, sometimes unbranched single lines (the former is much more common with CAs). The endpoints of those arms are the garden of eden states.
So, any garden of eden state leads through transient states to some attractor or cycle state. Transient states need not be garden of eden states - they lead (in general) through other transient states to an attractor or cycle state. States on the cycles or attractors visit the rest of the states on that cycle, then repeat.
In some cases you get one large cycle with all the transients falling onto it. (Prime widths promote this). In others you get multiple cycles, sometimes similar to each other (4 similar copies e.g., differing only in "phase" effectively), occasionally some not (a large cycle and some other smaller ones like the previous) etc.
On two, yes it is well known that rule 73 without vertical stripes gives a class 3 looking ongoing random behavior. This can already be seen in rule 73 from a single black cell initial condition, and is discussed in the NKS book starting on page 699. There are also some notes about it.
The different behaviors of rule 73 are one of the pieces of suggestive evidence Wolfram cites for the conjecture that class 3 rules might eventually be found that support universality. More generally, special classes of initials (periodic e.g., or in this case no block of 2 1s repeated, etc) can make some 3s behave in ways different from their usual behavior from random initials, and it might be possible to exploit this - and different wide regions started differently - to get them to behave in ways controllable enough to support universality constructions.
Fine questions, and I hope this helps.
Posted by: green_meklar
Yes, that answers my questions pretty well. I'm not too well versed in NKS terminology, but I think I understood everything you said. Thanks! :)
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings