https://doi.org/10.1140/epjb/e2009-00147-x
Scale-invariant cellular automata and self-similar Petri nets
1
Algorithmics, Parkring 10, 1010 Vienna, Austria
2
Institut für Theoretische Physik, University of Technology Vienna, Wiedner Hauptstraße 8-10/136, 1040 Vienna, Austria
Corresponding author: a svozil@tuwien.ac.at
Received:
24
June
2008
Revised:
11
December
2008
Published online:
29
April
2009
Two novel computing models based on an infinite tessellation of space-time are introduced. They consist of recursively coupled primitive building blocks. The first model is a scale-invariant generalization of cellular automata, whereas the second one utilizes self-similar Petri nets. Both models are capable of hypercomputations and can, for instance, “solve” the halting problem for Turing machines. These two models are closely related, as they exhibit a step-by-step equivalence for finite computations. On the other hand, they differ greatly for computations that involve an infinite number of building blocks: the first one shows indeterministic behavior, whereas the second one halts. Both models are capable of challenging our understanding of computability, causality, and space-time.
PACS: 05.90.+m – Other topics in statistical physics, thermodynamics, and nonlinear dynamical systems / 02.90.+p – Other topics in mathematical methods in physics / 47.54.-r – Pattern selection; pattern formation
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2009
