Following a brief introduction to cellular automata, the formal notion of tessellation automata is advanced and a cellular computer using them is described. Potentially, this computer has the ability to do self-diagnosis and self-reconfiguration for internal faults without external assistance. Next, computational equivalence of Turing Machines and tessellation automata is demonstrated. This shows the powerful nature of tessellation automata. Following this, the existence of cyclic patterns with unique subpatterns is proven. These results are relied upon heavily for the remainder of this dissertation. Results which find the relation between growth rate and neighborhood index are then obtained and a solution to the synthesis problem is found. This demonstrates the existence of a local transformation whereby a given configuration can be generated from a single seed in the automaton. Next, results for single perturbations of the automaton are given and fall into two classes; restoration of equilibrium configurations and self-diagnosis. Restoration results demonstrate the existence of configurations which will immediately restore themselves following any single perturbation. Results obtained for self-diagnosis show that any single perturbation of certain configurations will be detected and the perturbed cell will be identified by its neighbors. Of particular interest is a result demonstrating the construction of a homomorphic self-diagnosing automaton for any given finite-state machine. Implications of the results obtained are discussed and some open problems are considered. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/38817 |
| Date | 15 July 2010 |
| Creators | Walters, S. M. |
| Contributors | Electrical Engineering |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Dissertation, Text |
| Format | iv, 158 leaves, BTD, application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | OCLC# 40274347, LD5655.V856_1977.W358.pdf |
Page generated in 0.0019 seconds