'Viral' Turing Machines, Computation from Noise and Combinatorial Hierarchies
This work addresses theoretical foundations of computation from noise, potentially for researchers in computational theory, but appears incremental as it builds on existing paradigms.
The paper extends interactive computation by transcribing a minimal Turing Machine into an asynchronous Cellular Automaton with exponential waiting times, creating a stochastic analog of computation, and introduces an Inductive Combinatorial Hierarchy toolbox for deriving recursive relations of statistical quantities.
The interactive computation paradigm is reviewed and a particular example is extended to form the stochastic analog of a computational process via a transcription of a minimal Turing Machine into an equivalent asynchronous Cellular Automaton with an exponential waiting times distribution of effective transitions. Furthermore, a special toolbox for analytic derivation of recursive relations of important statistical and other quantities is introduced in the form of an Inductive Combinatorial Hierarchy.