A one-dimensional cellular automaton is an infinite row of identical machines---the cells---which depend for their behaviour only on the states of their direct neighbours. This thesis introduces a new way to think about one-dimensional cellular automata. The formalism of Flexible Time allows one to unify the states of a finite number of cells into a single object, even if they occur at different times. This gives greater flexibility to handle the structures that occur in the development of a cellular automaton. Flexible Time makes it possible to calculate in an algebraic way the fate of a finite number of cells. In the first part of this thesis the formalism is developed in detail. Then it is applied to a specific problem of one-dimensional cellular automata, namely ether formation. The so-called ether is a periodic pattern of cells that occurs in some cellular automata: It arises from almost all randomly chosen initial configurations, and why this happens is not clear. For one of these cellular automata, the elementary cellular automaton with rule code 54, ether formation is expressed in the formalism of Flexible Time. Then a partial result about ether formation is proved: There is a certain fragment of the ether that arises with probability 1 from every random initial configuration, and it is then propagated with probability 1 to any later time. The persistence of the ether fragment is a strong argument that the ether under Rule 54 indeed arises from almost all input configurations. The result only requires that the states of the cells are chosen independently and with equal probability distributions, and that all cell states can occur. This is not yet a full proof of ether formation, but it is derived by formal means, not just by computer simulations.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:589112 |
| Date | January 2013 |
| Creators | Redeker, Markus |
| Publisher | University of the West of England, Bristol |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://eprints.uwe.ac.uk/22167/ |
Page generated in 0.0022 seconds