Complexity of Two-dimensional patterns
I haven't posted in the last couple of days, because I didn't see anything in the recent arXiv updates that caught my fancy.
Rather than let this go on, I'm posting about something that was written in 1997, but does catch my fancy.
One of the coolest and most effective techniques for studying one-dimensional cellular automata is the regular language method. I tried to write something about it for a class, and the professor put the class papers up on the web, which is embarrassing.
The idea is that, in most cellular automata, there are "gardens of eden" - patterns that never arise from running the rule. As a simple example, consider a rule where "every live cell with at least one live neighbor dies". After one step, the pattern will consist entirely of isolated live cells.
So if you're a CA researcher, and you want to know facts about a rule like "After one step, the pattern will consist entirely of isolated live cells". To translate that into jargon, you say "The finite time set at t=1 is the golden mean shift". ("finite time set" = "the set of patterns possible at a certain time" , and "golden mean shift" = "the set of strings of 0s and 1s that do not contain two adjacent 0s").
So the "regular language method" is just a result of Wolfram's that the finite time set of any 1-dimensional automaton, at any t, is a regular language.
This is cool, and there are various applications (for example, in filtering the space-time diagram of a CA to get particle dynamics - I haven't read "Computational Mechanics of Cellular Automata: an example" carefully yet, but I recommend it.). Still, one wonders why such a simple and reasonable technique has not been extended to the two-dimensional case.
"Complexity of Two-Dimensional Patterns" explains clearly (if you have some theory of computation background knowledge) why it is tricky to extend to the two-dimensional case.
You probably know that deterministic finite automata are equivalent to nondeterministic finite automata. It's easy to believe (though I don't remember hearing about it in class), that deterministic finite automata with the ability to move backward as well as forward on the input, are equivalent to ordinary DFAs. There are several more definitions of "regular language", all equivalent. Each of these definitions has a reasonable generalization to two dimensions. Unfortunately, they are no longer equivalent.
I recommend this paper.
Rather than let this go on, I'm posting about something that was written in 1997, but does catch my fancy.
One of the coolest and most effective techniques for studying one-dimensional cellular automata is the regular language method. I tried to write something about it for a class, and the professor put the class papers up on the web, which is embarrassing.
The idea is that, in most cellular automata, there are "gardens of eden" - patterns that never arise from running the rule. As a simple example, consider a rule where "every live cell with at least one live neighbor dies". After one step, the pattern will consist entirely of isolated live cells.
So if you're a CA researcher, and you want to know facts about a rule like "After one step, the pattern will consist entirely of isolated live cells". To translate that into jargon, you say "The finite time set at t=1 is the golden mean shift". ("finite time set" = "the set of patterns possible at a certain time" , and "golden mean shift" = "the set of strings of 0s and 1s that do not contain two adjacent 0s").
So the "regular language method" is just a result of Wolfram's that the finite time set of any 1-dimensional automaton, at any t, is a regular language.
This is cool, and there are various applications (for example, in filtering the space-time diagram of a CA to get particle dynamics - I haven't read "Computational Mechanics of Cellular Automata: an example" carefully yet, but I recommend it.). Still, one wonders why such a simple and reasonable technique has not been extended to the two-dimensional case.
"Complexity of Two-Dimensional Patterns" explains clearly (if you have some theory of computation background knowledge) why it is tricky to extend to the two-dimensional case.
You probably know that deterministic finite automata are equivalent to nondeterministic finite automata. It's easy to believe (though I don't remember hearing about it in class), that deterministic finite automata with the ability to move backward as well as forward on the input, are equivalent to ordinary DFAs. There are several more definitions of "regular language", all equivalent. Each of these definitions has a reasonable generalization to two dimensions. Unfortunately, they are no longer equivalent.
I recommend this paper.
posted by Johnicholas at 1:52 PM
0 Comments:
Post a Comment
<< Home