{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:19:38Z","timestamp":1780071578165,"version":"3.54.0"},"reference-count":43,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T00:00:00Z","timestamp":1595203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The open-domain Frame Problem is the problem of determining what features of an open task environment need to be updated following an action. Here we prove that the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable. We discuss two other open-domain problems closely related to the Frame Problem, the system identification problem and the symbol-grounding problem, and show that they are similarly undecidable. We then reformulate the Frame Problem as a quantum decision problem, and show that it is undecidable by any finite quantum computer.<\/jats:p>","DOI":"10.3390\/a13070175","type":"journal-article","created":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T06:08:17Z","timestamp":1595225297000},"page":"175","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Equivalence of the Frame and Halting Problems"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1410-0307","authenticated-orcid":false,"given":"Eric","family":"Dietrich","sequence":"first","affiliation":[{"name":"Department of Philosophy, Binghamton University, Binghamton, NY 13902, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4812-0744","authenticated-orcid":false,"given":"Chris","family":"Fields","sequence":"additional","affiliation":[{"name":"Department of Philosophy, Binghamton University, Binghamton, NY 13902, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,20]]},"reference":[{"key":"ref_1","unstructured":"Michie, D., and Meltzer, B. (1969). Some philosophical problems from the standpoint of artificial intelligence. Machine Intelligence, Edinburgh University Press."},{"key":"ref_2","unstructured":"Partridge, D. (1991). Engineering artificial intelligence applications in unstructured task environments: Some methodological issues. Artificial Intelligence and Software Engineering, Ablex."},{"key":"ref_3","unstructured":"Hookway, C. (1984). Cognitive wheels: The frame problem of AI. Minds, Machines and Evolution: Philosophical Studies, Cambridge University Press."},{"key":"ref_4","unstructured":"Pylyshyn, Z.W. (1987). Modules, frames, fridgeons, sleeping dogs, and the music of the spheres. The Robot\u2019s Dilemma, Ablex."},{"key":"ref_5","unstructured":"Pylyshyn, Z.W. (1987). What the frame problem is and isn\u2019t. The Robot\u2019s Dilemma, Ablex."},{"key":"ref_6","unstructured":"Pylyshyn, Z.W. (1987). We\u2019ve been framed: Or, why AI is innocent of the frame problem. The Robot\u2019s Dilemma, Ablex."},{"key":"ref_7","unstructured":"Ford, K.M., and Pylyshyn, Z.W. (1996). The role of the frame problem in Fodor\u2019s modularity thesis: A case study of rationalist cognitive science. The Robot\u2019s Dilemma Revisited, Ablex."},{"key":"ref_8","unstructured":"Fodor, J.A. (2008). The Language of Thought Revisited, Oxford University Press."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1080\/09672550802113235","article-title":"Cognition in context: Phenomenology, situated cognition and the frame problem","volume":"16","author":"Wheeler","year":"2010","journal-title":"Int. J. Philos. Stud."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.shpsa.2010.07.006","article-title":"Classical computationalism and the many problems of cognitive relevance","volume":"41","author":"Samuels","year":"2010","journal-title":"Stud. Hist. Philos. Sci. Part A"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s13164-013-0137-4","article-title":"What\u2019s the problem with the Frame problem?","volume":"4","author":"Chow","year":"2013","journal-title":"Rev. Philos. Psychol."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"M\u00fcller, V. (2016). Why emotions do not solve the frame problem. Fundamental Issues in Artificial Intelligence, Springer.","DOI":"10.1007\/978-3-319-26485-1"},{"key":"ref_13","unstructured":"Nobandegani, A.S., and Psaromiligkos, I.N. (2017). The causal Frame problem: An algorithmic perspective. Preprint, Available online: https:\/\/arxiv.org\/abs\/1701.08100."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Nakayama, Y., Akama, S., and Murai, T. (2018, January 5\u20138). Four-valued semantics for granular reasoning towards the Frame problem. Proceedings of the 2018 Joint 10th International Conference on Soft Computing and Intelligent Systems (SCIS) and 19th International Symposium on Advanced Intelligent Systems (ISIS), Toyama, Japan.","DOI":"10.1109\/SCIS-ISIS.2018.00018"},{"key":"ref_15","unstructured":"Zalta, E.M. (2016). The frame problem. The Stanford Encyclopedia of Philosophy, Stanford University. [Spring 2016 Edition]."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Dietrich, E. (2020). When science confronts philosophy: Three case studies. Axiomathes, Available online: https:\/\/link.springer.com\/article\/10.1007\/s10516-019-09472-9.","DOI":"10.1007\/s10516-019-09472-9"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Baldassarre, G., and Mirolli, M. (2013). Intrinsically motivated learning of real world sensorimotor skills with developmental constraints. Intrinsically Motivated Learning in Natural and Artificial Systems, Springer.","DOI":"10.1007\/978-3-642-32375-1"},{"key":"ref_18","first-page":"76","article-title":"Robot planning in the real world: Research challenges and opportunities","volume":"37","author":"Alterovitz","year":"2016","journal-title":"AI Mag."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s10846-019-01000-6","article-title":"Immunity-based dynamic reconfiguration of mobile robots in unstructured environments","volume":"96","author":"Raza","year":"2019","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On computable numbers, with an application to the Entscheid","volume":"42","author":"Turing","year":"1937","journal-title":"Proc. Lond. Math. Soc. Ser. 2"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1090\/S0002-9947-1953-0053041-6","article-title":"Classes of recursively enumerable sets and their decision problems","volume":"74","author":"Rice","year":"1953","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1080\/0952813X.2012.741624","article-title":"How humans solve the frame problem","volume":"25","author":"Fields","year":"2013","journal-title":"J. Expt. Theor. Artif. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"172","DOI":"10.3390\/info5010172","article-title":"Equivalence of the symbol grounding and quantum system identification problems","volume":"5","author":"Fields","year":"2014","journal-title":"Information"},{"key":"ref_24","unstructured":"Cleve, R., Hoyer, P., Toner, B., and Watrous, J. (2004, January 24). Consequences and limits of nonlocal strategies. Proceedings of the 19th IEEE Annual Conference on Computational Complexity, Amherst, MA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1088\/2058-7058\/3\/8\/26","article-title":"Against \u2018measurement\u2019","volume":"3","author":"Bell","year":"1990","journal-title":"Phys. World"},{"key":"ref_26","unstructured":"Ji, Z., Natarajan, A., Vidick, T., Wright, J., and Yuen, H. (2020). MIP* = RE. Preprint, Available online: https:\/\/arxiv.org\/abs\/2001.04383."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1147\/rd.53.0183","article-title":"Irreversibility and heat generation in the computing process","volume":"5","author":"Landauer","year":"1961","journal-title":"IBM J. Res. Dev."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1098\/rstb.2006.2004","article-title":"Socially intelligent robots: Dimensions of human\u2013robot interaction","volume":"362","author":"Dautenhahn","year":"2007","journal-title":"Philos. Trans. R. Soc. B"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Mahmoud Zadeh, S., Powers, D.M.W., and Bairam Zadeh, R. (2019). Advancing autonomy by developing a mission planning architecture (Case Study: Autonomous Underwater Vehicle). Autonomy and Unmanned Vehicles. Cognitive Science and Technology, Springer.","DOI":"10.1007\/978-981-13-2245-7"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s10846-017-0680-9","article-title":"Toward autonomous planetary exploration","volume":"93","author":"Schuster","year":"2019","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1098\/rstb.2008.0300","article-title":"Predictive coding under the free-energy principle","volume":"364","author":"Friston","year":"2009","journal-title":"Philos. Trans. R. Soc. Lond. B"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1017\/S0140525X12000477","article-title":"Whatever next? Predictive brains, situated agents, and the future of cognitive science","volume":"36","author":"Clark","year":"2013","journal-title":"Behav. Brain Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1037\/0033-295X.111.4.1036","article-title":"An integrated theory of the mind","volume":"111","author":"Anderson","year":"2004","journal-title":"Psych. Rev."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/TAMD.2013.2277589","article-title":"LIDA: A systems-level architecture for cognition, emotion and learning","volume":"6","author":"Franklin","year":"2014","journal-title":"IEEE Trans. Auton. Ment. Dev."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1080\/09528130701191560","article-title":"The importance of cognitive architectures: An analysis based on CLARION","volume":"19","author":"Sun","year":"2007","journal-title":"J. Expt. Theor. Artif. Intell."},{"key":"ref_36","unstructured":"Shannon, C.W., and McCarthy, J. (1956). Gedankenexperiments on sequential machines. Autonoma Studies, Princeton University Press."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Fields, C. (2018). Some consequences of the thermodynamic cost of system identification. Entropy, 20.","DOI":"10.3390\/e20100797"},{"key":"ref_38","unstructured":"Quine, W.V.O. (1960). Word and Object, MIT Press."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"326","DOI":"10.3390\/quantum2020022","article-title":"Holographic screens are classical information channels","volume":"2","author":"Fields","year":"2020","journal-title":"Quant. Rep."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.jmp.2018.06.001","article-title":"On universality of classical probability with contextually labeled random variables","volume":"85","author":"Dzhafarov","year":"2018","journal-title":"J. Math. Psychol."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195","article-title":"On the Einstein-Podolsky-Rosen paradox","volume":"1","author":"Bell","year":"1964","journal-title":"Physics"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1103\/RevModPhys.65.803","article-title":"Hidden variables and the two theorems of John Bell","volume":"65","author":"Mermin","year":"1993","journal-title":"Rev. Mod. Phys."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1103\/PhysRevLett.49.91","article-title":"Experimental realization of Einstein-Podolsky-Rosen-Bohm gedankenexperiment: A new violation of Bell\u2019s inequalities","volume":"49","author":"Aspect","year":"1982","journal-title":"Phys. Rev. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/7\/175\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:49:53Z","timestamp":1760176193000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/7\/175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,20]]},"references-count":43,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2020,7]]}},"alternative-id":["a13070175"],"URL":"https:\/\/doi.org\/10.3390\/a13070175","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,20]]}}}