Posted by Eric Rowland.
Tammaso Bolognesi, "Detecting and Measuring Randomness in Process-Algebraic Computations"
He described a process for obtaining a labeled tree from a "behavior expression". The tree gives the semantics (the parsing) of the expression. He was trying to find good two-dimensional (space-time) visual representations of these trees, specifically looking for randomness without universality -- contrary to the Principle of Computational Equivalence.
He has shown the universality of a certain process algebra specification by emulating rule 110 with it. But intrinsic randomness generation was surprisingly hard to find.
During questions, Stephen Wolfram mentioned powers of 3 in base 2 as another example of apparent randomness in the presence of reducibility and wondered about the general class of systems for which this occurs.
Ramon Alonso-Sanz, "Cellular Automata with Memory"
Standard "ahistoric" cellular automata have no memory. With full memory, all past cell states are taken into consideration. This causes an "inertial effect" in the evaluation.
The speaker showed analogies of the elementary cellular automata with various degrees of memory. All rules are somewhat affected by memory, but some more than others. Different ways of averaging yield different memory mechanisms. Examples were given of automata on hexagonal grids, reversible rules, and automata on networks.
To end, he showed the Salvador Dali "melting clocks" painting Persistence of Memory.
Thomas Worsch, "Observations (with Expanations?) in the Sandpile Model"
This talk discussed a two-dimensional rule with eight possible states (0 through 8), which can be thought of as a number of grains of sand. If a cell has more than 4 grains, it "fires" and moves 1 to each of its four neighbors. The examples shown were in a finite world, beginning with a border of high values and letting the "sand" propogate inward. The automaton always reaches a stable configuration.
A configuration is recurrent if and only if each cell fires precisely once. A configuration is transient if and only if there is at least one cell which never fires.
He showed a plot of the frequencies of state cells as a function of time. Very suddenly, the smooth curves just flatten out. The end frequencies are largely independent of size of the world. He suggests that the frequencies aren't "random" even though they look somewhat arbitrary.
A three-dimensional version of the sandpile automaton has been considered, and (by reducing from 3SAT) Matthias Schulz has shown that the following question is NP-complete: Given a transient configuration, what is the minimum number of grains we need to add in order to reach a recurrent configuration?
It is not known whether the same question is NP-complete for the two-dimensional case. (It is solvable in linear time in one dimension.)
Jurgen Kluver, Recent Results on Ordering Parameters in Cellular Automata and Boolean Networks
Ordering parameters are numbers which characterize rules, not just of cellular automato but more generally rules on a boolean network. The P-parameter and lambda-parameter both measure the proportion of different cell states generated by the respective cellular automaton or boolean network rules. He also discussed several others which measure different aspects.
There is an interesting "inequality" principle: The more unequal the various ordering parameters of a system are, the more simple the dynamics of the system will be (and vice versa).
So, how many parameters do we need to get an idea of the behavior of a system? The proposed answer is 3. Outside a hypothesized region in this 3-parameter space, complex dynamics occur with very low probability.