Nontrivial turmites are Turing-universal

MaRDI QIDQ5010155zbMATH OpenFDO

Authors Diego Maldonado, Anahí Gajardo, Benjamin Hellouin de Menibus, Andrés Moreir

Publication date 24 August 2021

Full work available at URL https://arxiv.org/abs/1702.05547, http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-13-number-5-6-2018/jca-13-5-6-p-373-392/

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity of Langton's ant
• The Complexity of Small Universal Turing Machines: A Survey
• The Complexity of Small Universal Turing Machines
• The complexity of small universal Turing machines: A survey
• scientific article; zbMATH DE number 4195207

Cites work

• scientific article; zbMATH DE number 1689044 (Why is no real title available?)
• scientific article; zbMATH DE number 5252388 (Why is no real title available?)
• P-completeness of Cellular Automaton Rule 110
• Universality in elementary cellular automata

Cited in

(3)

• Complexity of Langton's ant
• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• A physically universal Turing machine

This page was built for publication: Nontrivial turmites are Turing-universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5010155)