Pattern synthesis and perturbation in tessellation automata

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.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Electrical Engineering

Department dc:contributor.department

Electrical Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1977

Author dc:creator

• Walters, S. M.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Dc Identifier Other

etd-07152010-020359

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/38817