Recursive Abstractions and Approximate Models

Given my previous definition of system simulation (aka modelling) it seems intuitive that a finite system cannot model itself except insofar as it is itself. Even more obviously, no proper subsystem of a system could simulate its “parent”. A proper subsystem by definition has a smaller size than the enclosing system, but needs to be at least as big in order to model it.

(An infinite subsystem of an infinite system is not a case I care to think too hard about, though in theory it could violate this rule? Although some infinities are bigger than others, so… ask a set theorist.)

However, an abstraction of a system can be substantially smaller (i.e. require fewer bits of information) than the underlying system. This means that a system can have subsystems which recursively model abstractions of their parents. Going back to our game-of-life/glider example, this means that you could have a section of a game of life which computationally modeled the behaviour of gliders in that very same system. The model cannot be perfect (that would require the subsystem to be larger than its “parent”) so the abstraction must of necessity be incomplete, but as we saw in that example being incomplete doesn’t make it useless.

Modelling Systems

Now that we have the link between systems theory and information theory explicitly on the table, there are a couple of other interesting topics we can introduce. For example, the famous Turing machine can both:

  1. Be viewed as a system.
  2. Model (aka simulate) any other possible system.

And it is on the combination of these points that I want to focus. First, I shall define the size of a system as the total number of bits that are needed to represent the totality of its information. This can of course change as the entropy of the system changes, so the size is always specific to a particular state of a system.

With this definition in hand (and considering as an example the Turing machine above), we can say that a system can be perfectly simulated by any other system whose maximum size is at least as large as the maximum size of the system being simulated. The Turing machine, given its unlimited memory, has an infinite maximum size and can therefore simulate any system. This leads nicely to the concept of being Turing complete.

(Note that an unlimited memory is not in itself sufficient for Turing completeness. The system’s rules must also be sufficiently complex or else the entropy over time of the system reduces to a constant value.)