In this post, I've written something that would have been very helpful to my former self from a few years ago. Given that, it may or may not be helpful to anyone else.

When studying for agent foundations research, I kept finding that I wanted a good general formalism of "stuff happening over time". Applications include;

• Optimization happens over time.
• Agents make observations over time.
• Learning happens over time (although I consider learning theory to be mostly out of scope for my agenda).
• Agents have models of the environment; if the environment has type "stuff happening over time", then the models should maybe also have type "stuff happening over time". (But maybe not!)
• AI is implemented on computers, and computations are a subclass of "stuff happening over time". How does this interact with the above?

For quite a while, I felt pretty overwhelmed and disoriented about all the options. But over time I have slowly come to understand the shape of several sub-fields of mathematics that have their own rich theory of "stuff happening over time", complete with deep theorems and decades of literature. All of these seem potentially useful to me, and so I dovetail between them.^[1]

Some types of systems

I would be impossible to satisfactorily explain each of these types of systems. So instead, I'm just going to state a reference-level description of each, describing what its state space looks like and what kind of dynamics it uses, and just a bit of intuition or motivation.

I have also highlighted some canonical examples. Reading about this example until you feel like you "get" it is probably a fairly efficient way to get a lot of information about what this type of system is like.

Stochastic process

In a stochastic process, the world is a temporal sequence of random variables. The state of the system that you will observe at time t is sampled from the random variable indexed by t. Unlike the others on this list, here the dynamics themselves are considered non-deterministic; even if you know the value of the previous variables, then the next value is still drawn from a probability distribution, albeit one that is now conditioned on said values.

Key example: I.i.d. processes like repeated coin flips

Key example: Markov chains

Measure-preserving dynamics (especially ergodic theory)

Measure-theoretic probability is the field that well-defines how to work with manipulating probabilities when you want to take the conjunction or disjunction of infinitely many possibilities. (For example, P(n is even) is the same as saying P(n = 0 or n = 2 or n = 4 or ...) and this requires some care.)

The state space is a measure space (usually a probability space). The dynamics are a measure-preserving function.

Most of this body of theory is concerned with ergodicity and other types of "mixing". It is interested in understanding how much the dynamics of a particular system scramble up the state space over time. I think this is potentially important because if the state space necessarily gets all mixed up, then you can't optimize the state.

Key example: Irrational rotations

Key example: 2x mod 1 (has many names)

Topological dynamics (especially symbolic dynamics)

Topology is one of the most important types of structure in mathematics.^[2] One of the most common (and most intuitive) types of topologies is a distance metric, that is, a way to say how far apart any two points are in the normal sense. Given a topology, you can talk about things like convergence and continuity.

I'm a big fan of an alternative characterization, which is that "topology is the logic of finite observations". This bears much explanation, but suffice it to say that if you are making observations of an underlying state space, then I think it's appropriate to use a topological space to formalize those observations.

A topological dynamical system has a topological space as its state space, and a continuous function for its dynamics. To define optimization via attractors, one must use a topological system. Similar to the above, one can also often talk about degrees of "mixing" in a purely topological sense.

In symbolic dynamics, you consider possible observations at each time step. You then construct a topological system via all possible sequences of observations.

Key example: also the irrational rotations

Key example: Cantor space with the shift map

Computability

In computability theory, your state space is an infinite binary tape, along with the finite internal state of the Turing machine. Your dynamics are the finite collection of "if-then" conditions that define the particular Turing machine. (Note that computability theory does not usually think in these terms.)

For the purpose of modelling the world, we probably want to allow the dynamics to have some randomness. This can be done in a number of ways, including giving the Turing machine a read-only "tape" that is essentially filled with coin flips.

Key example: Reading most anything about computability theory will give you a good sense of this field.

Key example: deterministic finite automata

For the purposes of agent foundations, it's important to note that none of these types of systems are "open" or "interactive" as typically defined, so they need to be modified to acted upon by an agent.

Interactions between the types

I'll note that my main goal is not to find one big, all-encompassing generalization that unites these frameworks. I mean, I'm not not trying to do that, but it's not a priority. Theorems are tools that tell us things like, "insofar as the situation can be well-modeled by abstraction A, then B follows". AI systems will sometimes be well-modeled by different types of systems in different contexts, so theorems about each of them could be useful in those contexts.

It's also been interesting to notice how much these systems do interact in the literature. I started out in a phase of "I have no idea what the categories are", then moved into a phase of "I now feel that these categories are very clearly separated and well-defined", and am now moving into a phase of "hm, actually it seem like these categories are frequently blurred in practice".

For example, there is huge over lap between topology and measure theory. Their definitions are only a few symbols off, which is pretty suggestive. I'm currently reading through a book on ergodic theory, which is nominally a sub-field of measure theory. But I noticed topological concepts popping up often. Eventually, I started annotating the book with all the mentions of topology. One pattern I've found is that most of the definitions are purely measure-theoretic, but many of the meaty theorems require topological assumptions.

One type of measure space is a Borel measure, which is when you take a topological space and derive a measure space from it. It's very very common but by no means universal. It may be that I eventually decide that most useful examples are of this type.

Another example is that, since computability naturally happens on infinite binary strings, the state space (ignoring the machine state) has a natural topology and measure space, which comes from Cantor space.

Another thing that has historically confused me quite a bit is that stochastic processes and measure-preserving dynamical systems are essentially the same, but with very different perspectives. Given a system of one type, you can convert it to a system of the other type. Neither field mentions this almost ever, and it's unclear to me how much insight is being lost due to this.

Levels above mine

I have by no means gotten the sense that I am "done" with this branch of exploration. There are several other resources that I have attempted to read, but have given up on, because I clearly lack the prereqs. Perhaps I'll try again in 6 months.

The clear front-runner here is category theory. If you look at, for example the list of Safeguarded AI theory projects funded by ARIA, you'll see tons of category theory. I look forward to one day grokking categorical systems theory, coalgebras, and string machines.

1. ^{^}

   Much earlier in my learning journey, I wrote A dynamical systems primer for entropy and optimization, which is similar but focuses on classifying systems by the cardinality of their space and time. This is mostly orthogonal to the classification in this post, and less important.

2. ^{^}

   The thing about donuts and coffee cups is algebraic topology, which I think is a misleading example for most purposes.