Equivalence of the Frame and Halting Problems

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


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.



External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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

257 (#69,732)

6 months
57 (#66,952)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Eric Dietrich
State University of New York at Binghamton

Citations of this work

No citations found.

Add more citations