# Equivalence of the Frame and Halting Problems
## 2 Results
### Notation and Operational Set-up  
Consider an agent \(A\) that interacts with an environment \(E\). We intend \(A\) to be a physically-realizable agent, so we demand that \(A\)'s state space have only finite dimension \(dim(A)\). We can, for the present purposes, consider \(A\) to be a classical agent with a classical state space; we extend the model to the quantum case in Section 3.3 below. For simplicity, we consider only computational states of \(A\), each of which we require to be finitely specifiable, that is, without loss of generality, specifiable as a finite bit string. Hence \(A\) has finite computational resources, expends finite energy, and generates finite waste heat [27].  
The environment \(E\) with which \(A\) interacts is by stipulation open; we also assume that \(E\) is \"large\", that is, that it has dimension \(dim(E)>dim(A)\). All realistic non-artificial task environments are both large and open: these include practical robotic task environments including human interaction [28], undersea [29] and planetary [30] exploration as well as the general human environment. Robotic or other AI systems operating in such environments all face the FP; as noted earlier, practical FP solutions in such environments are heuristic and hence subject to unpredictable failure.  
What is of interest in characterizing \(E\) is the ability of \(A\) to extract information from \(E\) by interaction. As \(A\) is limited to finite, finite-resolution interaction with \(E\), we have:  
**Lemma 1** (No Full Access lemma).: _A finite observer \(A\) can access only a finite proper component \(E_{A}\) of a large open environment \(E\)._  
Proof.: \(A\) can allocate at most some proper subset of its state space to memory, hence it can represent at most some \(N<dim(A)\) components of the state space of \(E\).  
As an obvious corollary, \(A\) cannot determine \(dim(E)\).  
Given the No Full Access lemma, we can without loss of generality represent the problem set-up as shown in Figure 1. We assume that \(A\) has observational access to some finite-dimensional proper component \(E_{A}\) of \(E\), but no access to the remainder \(E_{U}\); \(E=E_{A}\sqcup E_{U}\), \(E_{A},E_{U}\
eq\emptyset\), where \(\sqcup\) indicates disjoint union. We assume that \(A\) has a perception module obtaining input from \(E_{A}\), an action module supplying input to \(E\), and a problem-solving module with access to two generative models, one of \(E\) and one of \(A\). We take the model of \(E\) to be constructed entirely on the basis of \(A\)'s inputs from \(E_{A}\); this loses no generality, as any finite agent capable of encoding the model _a priori_ would be subject to the same in-principle access restrictions as \(A\). The model of \(E\) has a proper component that models \(E_{A}\) based on observational outcomes obtained; the remainder models \(E_{U}\) via (deductive, inductive, or abductive) inferences executed by the problem solving module. This model of \(E_{U}\) may be radically incomplete, containing many \"unknown unknowns\"; given \(A\)'s inability to determine \(dim(E)\), these cannot be circumscribed. The inferences employed to construct the model of \(E_{U}\) cannot, moreover, be subjected to experimental tests except via their predicted consequences for the behavior of \(E_{A}\). For any physically-realizable agent, the models of \(E_{A}\) and \(E_{U}\) are clearly both finite and of finite resolution; similarly \(A\)'s \"self\" model must be both finite and of finite resolution.  
We can, clearly, think of \(A\) as a Turing machine with finite processing and input/output (I/O) tapes. We can, however, also think of \(A\) as a hierarchical Bayesian or other predictive-processing agent (e.g., References [31; 32]) or as an artificial neural network with weights stored in the \(E\) and self models. Agent architectures such as ACT-R [33], LIDA [34], or CLARION [35] can all be represented in the form of Figure 1.