scratch

So, the question is how to present nicely the Von Neumann's Universal Self-Replicator construction

One thing should be emphasized: unlike most math disciplines where we like to present things as a difficult challenge that one must overcome, as much as it is true that Von Neumann found a solution to a nontrivial problem, it turns out to contain much more wisdom than if we tried to solve a problem a minima

It is very important to understand the wisdom of this in presenting the automaton; it is by no means perfect, but there are essential qualities about Von Neumann's construction that further constructions do not necessarily possess

Von Neumann's Automaton

One of the difficult things about presenting Von Neumann's construction is that it is not extremely clear what problem is being solved

To start with, it is important to understand that there should be a quiescent state, because otherwise we can only store a finite amount of information

Then, a natural objection is that we could have an environment where things just replicate, and that is obviously not interesting at all

Somehow, it is very important to understand that there is some deep universality in the construction of Von Neumann

For instance... we would like to have a proof that the Game of Life admits universal self-replicators

Ultimately this quickly goes into nontrivial territory with e.g. open questions about reaction-diffusion models

The theorem that we actually proved

If we want to phrase the mathematical question that we are answering with the Von Neumann automaton's construction, it is: can we show that life in a medium exists against 'naive odds', i.e. if there is no self-replicator of size 100x100 for a nearest-neighbor 29-state automaton, we would not really expect there to be a self-replicator of size 1000x1000, yet this is what happens

March 11th, 2025

So, for the Kleene fixed-point theorem and the interaction with the wrapper, things are indeed clearer... and these wrapper ideas are actually the kind of things that we will need going forward with the universal kinematic cellular automaton problem

In terms of the topic for the next class, I think that it would make sense to speak about the game of life and the Moore and Myhill's theorem

I think that the topic of the Wolfram classification classes would be best left for the fifth lecture; that topic is already about the 'class of cellular automata'; it would make sense that the focus of the fourth lecture be on the configurations (which is definitely an under-rated side of the question, it is good to focus on configurations)

So, if we work with a specific automaton like the game of life, some questions become more natural, because a random configuration yields more naturally interesting stuff

It becomes pretty clear pretty fast that there are some questions like the presence of ancestors

This naturally leads to the Moore and Myhill theorem, where we get that there exists orphan (parentless) patterns whenever we have twin patterns (and vice versa); Gardens of Eden are just equivalent to orphan (parentless) patterns

A good strategy will be to present this for the game of life and to leave as an exercise to generalize to anything

Anyway, the Moore-Myhill theorem is a fancier version of statement about functions

f: S\to S

for finite sets

S

f\,\, injective\iff f\,\, surjective

The only thing we should be careful about is that we want to work with finite regions (the configurations there will be 'patterns'), so we should take care of the boundaries

Now, the lack of injectivity will translate into 'twins' or 'mutually erasable' patterns, i.e. a pair of patterns that get mapped to the same, no matter what is on the boundary

For the game of life, these are quite easy to find: just find something that e.g. dies off, and put a circuit around it

Then the orphan patterns are patterns that cannot be generated by anything (in one step), no matter what we would put on the boundary

So, if this were about a model with no influence from the boundary, this would be settled: two configurations get mapped to the same thing, and so naturally, there is something that is not in the image

Now, we should work a little bit more, because we should argue that for similar reasons the set of images must be too small for the surjectivity to happen if we have twin patterns

That's one direction (the slightly more interesting one)...

For the other direction, we should argue that if we are not surjective, we are not injective... so we should argue that if the image is small, there must be some squeeze

There is another statement about the Gardens of Eden, which is that they exist if and only if there are orphan patterns

March 17th, 2025

Ok, for Wednesday class, we should discuss cellular automata in more generality

The first lectures, we focused on the Von Neumann cellular automata, which was designed so that one could construct a universal self-replicator

Then we went to a slightly simpler cellular automaton, the Game of Life, which was designed for simplicity, and we showed interesting behaviors (which is the reason why people started caring about it)

And this then brings us to the space of automata, which is a huge space, and where people stopped wondering too much about the specific configurations

Before that, we should add our results about the theory of automata, saying first that there is an example of something that is Turing complete in one dimension, that there is an example of something that is self-replicating in one dimension, and that there is a kind of answer to the Toffoli construction problem

So... before we go to the more exotic zoology of CAs, there are questions about

•

Reversibility: in general, this is something that I find very interesting and deep, and perhaps we should discuss this before we discuss any of the other things... maybe it makes more sense, even that we focus on this first

•

The emergence of the various classes