Emergence of Metastable Mixed Choice in Probabilistic Induction
Burton Voorhees
Athabasca University
Full text:
PDF
Last modified: May 23, 2006
Abstract
Let {µ(t)} be a set of discrete time measurements of the state of a dynamical system S and let M be a set of evolution rules that are considered candidates for description of the dynamical rules governing S. We describe a probabilistic induction algorithm that provides an unbiased best guess estimate of the rule in M that generated the series {µ(t)}. In the particular case in which {µ(t)} is a set of mdigit binary strings and M is a set of elementary cellular automaton rules, this algorithm predicts with high probability as series generator a rule in a symmetry class containing the actual generating rule. What is of greater interest is the response of the algorithm when the series {µ(t)} is random. In this case the response of the algorithm allows exploration of subtle structure within cellular automata rule space. In addition, cases arise in which the induction algorithm only yields a mixed choice, that is, is unable to decide among a small set (2  5) of rules. These "faceoff" cases appear to be stable: whereas winning rules emerge within a few thousand iterations of the algorithm, faceoffs persist up to the upper limit of 100,100 iterations. This is counterintuitive since it requires that the choice probability of a rule decrease when that rule is chosen at any given iteration. In this talk we describe the induction algorithm, illustrate some of the relations it shows within cellular automata rule space, and present an analysis of the paradoxical faceoff cases.


