Zeno Squeezing of Cellular Automata
Martin Schaller and Karl Svozil
We have recently introduced two new models of computations: self-similar cellular automata and self-similar Petri nets. Self-similar automata result from a progressive, infinite tessellation of space and time. Self-similar Petri nets consist of a potentially infinite sequence of coupled transitions with ever increasing firing rates. Both models are capable of hypercomputations and can, for instance, “solve” the halting problem for Turing machines. We survey the main theory, state a new proposition about the indeterminism of self-similar cellular automata and present a simplified construction of a hypercomputer within self-similar cellular automata.
Keywords: Hypercomputers, cellular automata, Petri nets, Zeno’s paradox