2026-08-17T16:46:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19909 2024-06-03T07:31:39Z ddc:004 open_access

Baba Is Universal Abel, Zachary Hendrickson, Della Undecidability Baba is You RE-hardness counter machines universal computation We consider the computational complexity of constant-area levels of games which allow an unlimited number of objects in a fixed region. We discuss how to prove that such games are RE-hard (and in particular undecidable) and capable of universal computation, even on constant-area levels. We use the puzzle game Baba is You as a case study, showing that 8×17 levels are capable of universal computation by constructing a particular small universal counter machine within Baba is You. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zachary Abel and Della Hendrickson 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.1 urn:nbn:de:0030-drops-199093 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.1 eng https://creativecommons.org/licenses/by/4.0/legalcode