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.