Scale-invariant cellular automata and self-similar Petri nets

Abstract

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.

35 pages, 5 figures

References in corpus (2)

• Hypercomputation: computing more than the Turing machine
• The Church-Turing thesis as a guiding principle for physics

Cited by in corpus (2)

• Zeno Squeezing of Cellular Automata
• On the brightness of the Thomson lamp. A prolegomenon to quantum recursion theory