A universal cellular automaton in quasi-linear time and its S-m-n form

DOI10.1016/0304-3975(92)00076-4zbMath0801.68116OpenAlexW2075471429MaRDI QIDQ1314380

Bruno Martin

Publication date: 29 November 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)00076-4

zbMATH Keywords

parallel computationTuring machineprogramming languagestructural complexitytransition functionsrecursive specificationsacceptable programming systembrick languagequasi-linear time universal cellular automatonS-m-n theorem

Mathematics Subject Classification ID

Theory of programming languages (68N15) Specification and verification (program logics, model checking, etc.) (68Q60) Cellular automata (computational aspects) (68Q80)

Related Items (14)

Intrinsic universality of a 1-dimensional reversible Cellular Automaton ⋮ Grids and universal computations on one-dimensional cellular automata ⋮ Cellular automata universality revisited ⋮ A single-copy minimal-time simulation of a torus of automata by a ring of automata ⋮ On Goles' universal machines: a computational point of view ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage ⋮ Abstract geometrical computation. 11: Slanted firing squad synchronisation on signal machines ⋮ Bulking I: An abstract theory of bulking ⋮ Achieving Universal Computations on One-Dimensional Cellular Automata ⋮ A simulation of cellular automata on hexagons by cellular automata on rings ⋮ On hardest languages for one-dimensional cellular automata ⋮ Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems ⋮ Inducing an order on cellular automata by a grouping operation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On real-time cellular automata and trellis automata
• A linear speed-up theorem for cellular automata
• Real-time language recognition by one-dimensional cellular automata
• An 8-state minimal time solution to the firing squad synchronization problem
• An optimum solution to the firing squad synchronization problem
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• Simple Computation-Universal Cellular Spaces

This page was built for publication: A universal cellular automaton in quasi-linear time and its S-m-n form