# Equivalence of the Frame and Halting Problems
## 1 Introduction  
The Frame Problem (FP) was introduced by [PERSON] and [PERSON] [1] as the problem of circumscribing the set of axioms that must be deployed in a first-order logic representation of a changing environment. From an operational perspective, it is the problem of circumscribing the set of (object, property) pairs that need to be updated following an action. In a fully-circumscribed domain comprising a finite set of objects, each with a finite set of properties, the FP is clearly solvable by enumeration; in such domains, it is merely the problem of making the enumeration efficient. Fully-circumscribed domains are, however, almost by definition artificial [2]. In open domains, including task environments of interest for autonomous robotics, the ordinary world of human experience, or the universe as a whole, the FP raises potentially-deep questions about the representation of causality and change, particularly the representation of unobserved changes, e.g., leading to unanticipated side-effects. Interest in these questions in the broader cognitive science community led to broader formulations of the FP as the problem of circumscribing (generally logical) relevance relations [3, 4], a move vigorously resisted by some AI researchers [5, 6]. The FP in its broader formulation appears intractable; we have previously argued that it is in fact intractable on the basis of time complexity [7]. However, general discussion of the FP has remained largely qualitative (e.g., References [8, 9, 10, 11, 12, 13, 14]; see References [15, 16] for recent reviews) and the question of its technical tractability in a realistic, uncircumscribed operational setting remains open. Practical solutions to the FP, particularly in robotics, remain heuristic (e.g., References [17, 18, 19]). Here we show that in a fully-general, operational setting, the open-domain FP (hereafter, \"FP\") is equivalent to the Halting Problem (HP). The HP is the problem of constructing an oracle \(f(a,i)\), \(a\) an algorithm and \(i\) an input, such that \(f(a,i)=1\) if \(a\) given \(i\) halts in finite time and \(f(a,i)=0\) otherwise. That no such oracle can be implemented by a finite Turing machine (TM) was demonstrated by [PERSON] [20]. The HP has since been widely regarded as the canonical undecidable problem; proof of equivalence to the HP is proof of (finite Turing) undecidability. The FP is, therefore, undecidable and hence strictly unsolvable by finite means. This same result can also be obtained via [PERSON]'s Theorem [21]: supposing that a set of programs solving the FP exists, membership in that set is undecidable. If identity over time is regarded as a property of an object or more generally, a system, the problem of re-identifying objects or systems as persistent individuals is equivalent to the FP [22]. If the denotation of a symbol is a persistent object or set of objects, the symbol grounding problem is equivalent to the object identification problem [23] and hence to the FP. Undecidability of the FP renders these problems undecidable. To further investigate these issues, we here reformulate the FP as a quantum decision problem (the \"QFP\") faced by a finite-dimensional quantum computer, and show that this quantum version is also undecidable. We then show that the construction of a two-prover interactive proof system in which the provers share an entangled state [24] requires a solution to the QFP, which given its unsolvability can only be heuristic or \"FAPP\" (for all practical purposes; see Reference [25] where \"FAPP\" was introduced as a pejorative term). Given the recent proof of [PERSON] et al. that MIP* = RE [26], MIP* indicating languages decidable by a multiprover interactive proof system with shared entanglement and RE the recursively enumerable languages, we here conjecture that the QFP is not only strictly harder than the HP, but that it is outside RE. The FP being unsolvable by finite systems, whether classical or quantum, renders computational models of relevance, causation, identification, and communication equally intractable.