Exotic Automata: Extending Computational Theory
Listed in
This article is not in any list yet, why not save it to one of your lists.Abstract
Classical automata theory provides foundational models of computation and rests on specific assumptions regarding state, transitions, information, and structure. We argue that computation, as a broader concept encompassing dynamics observed in nature and mathematics, necessitates a theoretical expansion beyond these classical confines. This paper introduces Exotic Automata (EAs) – a system for formally defining and analyzing computational models characterized by principled divergences from classical assumptions. We establish a classification structure based on fundamental dimensions of divergence (Ontological, Operational, Structural, Temporal, Logical), revealing classical models as a specific instance within this larger landscape. Key EA classes are derived by modifying core classical tenets. These are illustrated through exemplar models, with their unique properties now more formally grounded within this paper. Examples include Structural Plasticity in Dynamic Interaction Graph Automata (DIGA), capable of self-rewiring; Computational Phase Transitions in Resource-Gated Turing Machines (RGTM), exhibiting pattern-sensitive speed fluctuations; Predictive Information Dynamics in Predictive History Automata (PHA), using memory for constraint and potentially achieving apparent entropy reduction through information reification; Fundamental Non-Locality exploration with Quantum Harp Coupled Automaton Systems (QHCAS); and modeling Alternative Operational Dimensions with OD=1 ``Noton'' Automata. We discuss how EAs compel new perspectives on computational complexity, necessitate novel simulation methodologies, and offer powerful tools for modeling complex phenomena. The EA framework represents a significant extension to computation theory, enabling a more rigorous exploration of the full spectrum of possible computational dynamics.