Is there any work that is about modeling embedded agency in a cellular automata? That seems like an obvious thing to do. I am asking in general and specifically in the context of solving embedded agency using these assumptions. All of these assumptions seem straightforward to get in a cellular automata.
E.g. one assumption is:
The world and the agent are both highly compressible. This means we can have a representation of the entire environment (including the agent) inside the agent, for some environments. We only concern ourselves with environments where this is the case.
You can get such a compressible environment easily by having it be mostly empty. Then you can use a sparse representation of the environment, which then will be a lot smaller than the environment.
Ideally, we want to end up with some system that works in a cellular automaton in a way that is computationally tractable. But here I am mainly thinking about making conceptual progress by theoretical analysis. I expect the concreteness of imagining a specific cellular automaton to be helpful. The goal would be to get a specification for a system that we can show would solve the problem discussed in this post.
You could also make it easy for the agent to manipulate the environment by having the physics of the environment be such that a specific configuration of cells corresponds to calling an external function with some arguments. External functions can then do things like:
Set a single-cell state.
Fill in a region. (includes the previous function)
Fill in the grid according to some provided functions. (includes the previous functions)
The naïve way to do this would probably still be intractable in practice, but it might make things easier to reason about conceptually, as the steps in the plan don’t need to contain complicated procedures for setting cell states. E.g. in the game of life you would only need to construct a function call, instead of constructing a spaceship that flies somewhere and then terraforms the environment.