Algorithms 13 (175):1-9 (2020)

Eric Dietrich
State University of New York at Binghamton
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.
Keywords Artificial Intelligence  Entanglement  Heuristic Search  Robotics  Frame Problem  Task Domain  Separability  Intractability
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

The Frame Problem.Murray Shanahan - 2008 - Stanford Encyclopedia of Philosophy.
Socially Intelligent Robots: Dimensions of Human-Robot Interaction.Kerstin Dautenhahn - 2007 - In Nathan Emery, Nicola Clayton & Chris Frith (eds.), Social Intelligence: From Brain to Culture. Oxford University Press.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

What’s the Problem with the Frame Problem?Sheldon J. Chow - 2013 - Review of Philosophy and Psychology 4 (2):309-331.
The Frame Problem: An AI Fairy Tale. [REVIEW]Kevin B. Korb - 1998 - Minds and Machines 8 (3):317-351.
Animals as Cost‐Based Robots.David McFarland - 1992 - International Studies in the Philosophy of Science 6 (2):133 – 153.
The Frame Problem and Theories of Belief.Scott Hendricks - 2006 - Philosophical Studies 129 (2):317-33.
Framing the Frame Problem.Eric Lormand - 1990 - Synthese 82 (3):353-74.
Five Formulations of the Quantum Measurement Problem in the Frame of the Standard Interpretation.Manuel Bächtold - 2008 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 39 (1):17-33.


Added to PP index

Total views
127 ( #92,124 of 2,508,112 )

Recent downloads (6 months)
24 ( #36,232 of 2,508,112 )

How can I increase my downloads?


My notes