This post is a draft, a work in progress. Much of it will not make sense, and will not be optimized for the reader's experience. It does not necessarily reflect my current best understanding of optimization. Like the introduction draft, I'm opening it up because I've been working on this project for too long, and the world is moving too fast. I want people to more easily be able to interact with my research thoughts as I'm having them.


We left off with an argument by analogy of how we could use Kolmogorov complexity as an "objective" means to infer the presence of optimization in a system. But how exactly, does that analogy carry over? How exactly do we use K-complexity in the context of dynamical systems trajectories?

In this post, I'll treat what I would call the "easy" case. The cases are formed by the structure of the state orders, so let's dig deeper into that.

Order shapes

In the introduction post, I talked about how the optimization target or criterion could be represented by a mathematical object called an order. Orders get pretty interesting once you start to include orders over infinite sets. In some sense, you could say that finite orders differ only in how they order things, but that infinite orders can differ in how they are "shaped". Consider this example

  • The typical ordering over the integers
  • The ordering over the integers provided by absolute value

The typical ordering has no least or greatest element; for every integer, you can find one that is higher in the ordering, and one that is lower. But in the absolute value order, there is a specific least element; 0. (And, of course, no greatest element.)

You can get pretty crazy with this. Here are some more examples.

[TODO just definitely pictures for all of these]

  • The natural numbers with the typical ordering, except you declare that 0 is the greatest element.
  • The integers ordered by 
  • Collate the natural numbers by their lowest divisor. E.g. everything divisible by 2 is lower than everything divisible by 3 (but not 2) and 2 is still lower than 4.

This is a way in which orders can have fundamentally different structures; two orders with the same "shape" can have a bijection (i.e. a relabeling of states) between them such that the ordering is preserved, but orders with different shapes do not have such a bijection.

Minimizers vs maximizers

An ordering either has a least element, or it does not have a least element.


[Reminder that this post is an open draft.]

New Comment