Cellular automata and the halting problem

homeblogtwitterthingiverse



Recently read Cellular Automata: a discrete universe by Andrew Ilachinsky. Very broad ranging. Anyway, one idea that hit home was an possible equivalence between the "edge of chaos" seen in cellular automata and the halting problem.

The halting problem is to determine whether a particular Turing Machine, when given a particular tape, will ever reach a certain state (the halt state). A general solution to this is of course impossible, but we can rule out most (for a particular definition of most) tapes and machines immediately as definitely either halting or non-halting.

An equivalent problem would be to ask if a Turing Machine will ever go into an infinite loop when given a particular tape, ie whether any tape/position/machine-state will ever repeat. An equivalent problem is to ask, with a particular set of cellular automata rules, when given a particular configuration of initial cell values, will an automata ever start repeating itself. (proof is left as an exercise to the reader :-P)

Again we could assign most (for a particular definition of most) rules and initial configurations to either looping or non looping. Ilachinsky makes the link that the rules for which doing so is hard or impossible -- the "edge of chaos" -- correspond to cases of the halting problem that are similarly hard or impossible.

Note that "chaos" does not mean true randomness, only pseudo-randomness. A seemingly random configuration generated by an automata contains no more information than saying "Iterate rule set X for Y iterations starting with configuration Z".

This all seems terribly important, though i'm not certain why.




[æ]