{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/150149"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/150149","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Unsimulability, Universality, and Undecidability in the Gizmo Framework","abstract":"The gizmo framework is a recent development of the gadget framework used for proving computational complexity results of videogames and other motion planning problems. This thesis explores three aspects of the gizmo framework: unsimulability (the inability of one gizmo to simulate another gizmo), universality (the ability of a gizmo to simulate all gizmos in its simulability class), and undecidability (the inability to decide whether a maze made of a gizmo is solvable). We give a proof that the 1- toggle cannot simulate the 2-toggle, as it contains important techniques. We explore a class of gizmos called dicrumbler variants, and give partial results for which ones simulate which others. We give universal gizmos for simulability classes Reg and DAG, and explore the concept of finding all the gizmos that simulate a particular gizmo, with partial results given for the dicrumbler. We show that reachability for a gizmo representing a counter in a counter machine is undecidable, and show several gizmo simulations. We give a proof that generalized New Super Mario Bros. is undecidable using one of the undecidable gizmos.","abstract_html":"The gizmo framework is a recent development of the gadget framework used for proving computational complexity results of videogames and other motion planning problems. This thesis explores three aspects of the gizmo framework: unsimulability (the inability of one gizmo to simulate another gizmo), universality (the ability of a gizmo to simulate all gizmos in its simulability class), and undecidability (the inability to decide whether a maze made of a gizmo is solvable). We give a proof that the 1- toggle cannot simulate the 2-toggle, as it contains important techniques. We explore a class of gizmos called dicrumbler variants, and give partial results for which ones simulate which others. We give universal gizmos for simulability classes Reg and DAG, and explore the concept of finding all the gizmos that simulate a particular gizmo, with partial results given for the dicrumbler. We show that reachability for a gizmo representing a counter in a counter machine is undecidable, and show several gizmo simulations. We give a proof that generalized New Super Mario Bros. is undecidable using one of the undecidable gizmos.","abstract_has_math":false,"creators":["Ani, Joshua"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Demaine, Erik D."],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-02","date_published":"2023-02","updated_at":"2026-07-22T22:22:19Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/150149","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Demaine, Erik D."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Ani, Joshua"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-03-31T14:35:50Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-03-31T14:35:50Z"]},{"key":"dc:date.issued","label":"Date","values":["2023-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Engineering in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/150149"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The gizmo framework is a recent development of the gadget framework used for proving computational complexity results of videogames and other motion planning problems. This thesis explores three aspects of the gizmo framework: unsimulability (the inability of one gizmo to simulate another gizmo), universality (the ability of a gizmo to simulate all gizmos in its simulability class), and undecidability (the inability to decide whether a maze made of a gizmo is solvable). We give a proof that the 1- toggle cannot simulate the 2-toggle, as it contains important techniques. We explore a class of gizmos called dicrumbler variants, and give partial results for which ones simulate which others. We give universal gizmos for simulability classes Reg and DAG, and explore the concept of finding all the gizmos that simulate a particular gizmo, with partial results given for the dicrumbler. We show that reachability for a gizmo representing a counter in a counter machine is undecidable, and show several gizmo simulations. We give a proof that generalized New Super Mario Bros. is undecidable using one of the undecidable gizmos."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Unsimulability, Universality, and Undecidability in the Gizmo Framework"]}]}],"canonical_facts":{"dc:contributor.advisor":["Demaine, Erik D."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Ani, Joshua"],"dc:date.accessioned":["2023-03-31T14:35:50Z"],"dc:date.available":["2023-03-31T14:35:50Z"],"dc:date.issued":["2023-02"],"dc:description.abstract":["The gizmo framework is a recent development of the gadget framework used for proving computational complexity results of videogames and other motion planning problems. This thesis explores three aspects of the gizmo framework: unsimulability (the inability of one gizmo to simulate another gizmo), universality (the ability of a gizmo to simulate all gizmos in its simulability class), and undecidability (the inability to decide whether a maze made of a gizmo is solvable). We give a proof that the 1- toggle cannot simulate the 2-toggle, as it contains important techniques. We explore a class of gizmos called dicrumbler variants, and give partial results for which ones simulate which others. We give universal gizmos for simulability classes Reg and DAG, and explore the concept of finding all the gizmos that simulate a particular gizmo, with partial results given for the dicrumbler. We show that reachability for a gizmo representing a counter in a counter machine is undecidable, and show several gizmo simulations. We give a proof that generalized New Super Mario Bros. is undecidable using one of the undecidable gizmos."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/150149"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Unsimulability, Universality, and Undecidability in the Gizmo Framework"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:22:19Z"}