Abstract
Rule 110 is a complex cellular automaton (CA) in Wolfram's system of identification, capable of supporting universal computation. It has been suggested that a universal CA should be on the ‘edge of chaos’, which means that the dynamical behaviour of such a system is neither simple nor chaotic. There is no doubt that the dynamical property of Rule 110 is extremely complex and still not well understood. This paper proves the existence of subsystems on which this rule is chaotic in the sense of Devaney.
Acknowledgements
This research was jointly supported by the NSFC (Grants No. 11171084 and No. 60872093) and the Hong Kong Research Grants Council (Grant No. CityU1117/10).