Turing Tumble is P(SPACE)-complete

DOI10.1007/978-3-030-17402-6_23MaRDI QIDQ2294057zbMATH OpenOpenAlexFDO

Authors Matthew P. Johnson

Publication date 6 February 2020

Full work available at URL https://doi.org/10.1007/978-3-030-17402-6_23

Mathematics Subject Classification ID

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

Recommendations

• Turing Tumble is Turing-complete
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Magic: The Gathering is Turing complete
• The PSPACE-Completeness of Black-White Pebbling
• scientific article; zbMATH DE number 2086639

Cited in

(4)

• Turing Tumble is Turing-complete
• Universal logic elements constructed on the Turing tumble
• Magic: The Gathering is Turing complete
• Universality of Turing Tumble of finite size

This page was built for publication: Turing Tumble is P(SPACE)-complete

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