Zeno Squeezing of Cellular Automata

Abstract

We have recently introduced the two new computing models of 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 definitions and propositions and add new results regarding the indeterminism of self-similar cellular automata.

16 pages, contribution to UC09

References in corpus (2)

• The Church-Turing thesis as a guiding principle for physics
• Scale-invariant cellular automata and self-similar Petri nets