The world of simple programs

• If a CA is too simple the behaviour is boring (static or repetitive)
• adding more power to the rules makes nesting possible
• ...and adding a bit more still can generate behaviour of great complexity
  • the threshold for complexity is amazingly low
  • above the threshold, adding more flexibility to the underlying rules doesn't lead to more complexity in the behaviour
• Many systems other than cellular automata show similar phenomena
  • mobile automata, Turing machines, substitution systems, tag systems, register machines, symbolic systems