6533b854fe1ef96bd12adead

RESEARCH PRODUCT

A New Universal Cellular Automaton Discovered by Evolutionary Algorithms

Olivier BailleuxPierre ColletEmmanuel SapinJean-jacques Chabrier

subject

Block cellular automatonTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer sciencebusiness.industryContinuous automatonNonlinear Sciences::Cellular Automata and Lattice GasesCellular automatonReversible cellular automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESStochastic cellular automatonElementary cellular automatonWolfram codeLife-like cellular automatonArtificial intelligencebusinessComputer Science::Formal Languages and Automata TheoryMathematics

description

In Twenty Problems in the Theory of Cellular Automata, Stephen Wolfram asks “how common computational universality and undecidability [are] in cellular automata.” This papers provides elements of answer, as it describes how another universal cellular automaton than the Game of Life (Life) was sought and found using evolutionary algorithms. This paper includes a demonstration that consists in showing that the presented R automaton can both implement any logic circuit (logic universality) and a simulation of Life (universality in the Turing sense).

yearjournalcountryeditionlanguage
2004-01-01
https://doi.org/10.1007/978-3-540-24854-5_16