From the discussions with Jordan and Bara came an idea that looks quite attractive

From the discussions with Jordan and Bara came an idea that looks quite attractive

There is some idea that we could call 'local Turing universality', and it says we should be able to construct any Turing machine within the cellular automaton via some embeddings (there are some small technicalities there, but that is the idea, basically)

There is some idea that we could call 'local Turing universality', and it says we should be able to construct any Turing machine within the cellular automaton via some embeddings (there are some small technicalities there, but that is the idea, basically)

And then there is the idea that a cellular automaton could be in some sense universal if it can, via some suitable coarse-graining, simulate any other cellular automaton

And then there is the idea that a cellular automaton could be in some sense universal if it can, via some suitable coarse-graining, simulate any other cellular automaton

Obviously, if we are in the latter category, we are necessarily locally universal: global universality implies local universality

Obviously, if we are in the latter category, we are necessarily locally universal: global universality implies local universality

Now, something that could be interesting in the process of showing that there exists CA rules with local universality but not global universality

Now, something that could be interesting in the process of showing that there exists CA rules with local universality but not global universality

The class that was suggested by Jordan is to construct something out of a reversible cellular automaton, and that seems like a very promising idea

The class that was suggested by Jordan is to construct something out of a reversible cellular automaton, and that seems like a very promising idea

So what we need is assume that we have a 2D cellular automaton that is reversible and universal, assume that it can e.g. simulate the game of life, and arrive at a contradiction

So what we need is assume that we have a 2D cellular automaton that is reversible and universal, assume that it can e.g. simulate the game of life, and arrive at a contradiction

Does the following work?

Does the following work?

We want to argue that a 2D reversible cellular automaton cannot be globally universal (even though it can be locally universal)

We want to argue that a 2D reversible cellular automaton cannot be globally universal (even though it can be locally universal)

If we run hash functions to determine the next states in parallel, and freeze the dynamics once a certain pattern is reached, then ultimately everything freezes, but I would tend to think that we can't reverse the dynamics completely: there is so much information in the the history that it would seem impossible that this information could be hidden in the 'microscopic' details that we are allowed to store via the 'coarse-graining ambiguity'

If we run hash functions to determine the next states in parallel, and freeze the dynamics once a certain pattern is reached, then ultimately everything freezes, but I would tend to think that we can't reverse the dynamics completely: there is so much information in the the history that it would seem impossible that this information could be hidden in the 'microscopic' details that we are allowed to store via the 'coarse-graining ambiguity'

A way simpler dynamics

A way simpler dynamics

A cellular automaton where everything goes to the quiescent state should work also... if we wait for a long enough time, and reverse the dynamics, it is impossible that the reversed system can 'wait' in a quiescent state for 'arbitrarily long' before 'popping up' to life

A cellular automaton where everything goes to the quiescent state should work also... if we wait for a long enough time, and reverse the dynamics, it is impossible that the reversed system can 'wait' in a quiescent state for 'arbitrarily long' before 'popping up' to life

A simple way to make things rigorous

A simple way to make things rigorous

Working on a torus is a simple way to ensure that things are finite, if we are to work by contradiction, in general

Working on a torus is a simple way to ensure that things are finite, if we are to work by contradiction, in general

Turing-Universal $\overset {?}\implies$ Self-Reproducing

Turing-Universal $\overset {?}\implies$ Self-Reproducing

Jordan somehow believes that the answer to this question is 'no' (i.e. that something that I dubbed 'anti-virus' software can be created)

Jordan somehow believes that the answer to this question is 'no' (i.e. that something that I dubbed 'anti-virus' software can be created)

February 10th, 2025

February 10th, 2025

I am not completely certain about that, in fact... but a class of ideas that could be promising if we believe this is to have a state with an energy value (it's also a bit similar to an idea that Vass had, I think), and that energy would globally be non-increasing

I am not completely certain about that, in fact... but a class of ideas that could be promising if we believe this is to have a state with an energy value (it's also a bit similar to an idea that Vass had, I think), and that energy would globally be non-increasing

So, there would be no 'energy doubling' if we had some energy conservation; of course, this does not preclude _some_ structures from being potentially able to reproduce

So, there would be no 'energy doubling' if we had some energy conservation; of course, this does not preclude some structures from being potentially able to reproduce

Somehow, I think that taking the energy into account is a little unfair (we can't duplicate energy and resources either, and this is why we can't reproduce ad infinitum)... it still could be useful to highlight that self-reproduction should not be understood in a super-strict sense

Somehow, I think that taking the energy into account is a little unfair (we can't duplicate energy and resources either, and this is why we can't reproduce ad infinitum)... it still could be useful to highlight that self-reproduction should not be understood in a super-strict sense

And if we are to define self-reproduction in a looser sense, then I become somehow more skeptical that it can even be impossible... can we construct a 'local antivirus' that _abstractly detects_ the notion of self-replication and reacts to that?

And if we are to define self-reproduction in a looser sense, then I become somehow more skeptical that it can even be impossible... can we construct a 'local antivirus' that abstractly detects the notion of self-replication and reacts to that?

It feels to me that detecting self-reproduction without any specific size constraint could amount to somehthing like the halting problem...

It feels to me that detecting self-reproduction without any specific size constraint could amount to somehthing like the halting problem...

Still, we could imagine something that would kind of compute a Fourier transform of things in space (the continuous Fourier transform can be computed by integrating a local PDE... should that be relevant), and if something became too periodic (at some scale...), then it would trigger something that would destroy all

Still, we could imagine something that would kind of compute a Fourier transform of things in space (the continuous Fourier transform can be computed by integrating a local PDE... should that be relevant), and if something became too periodic (at some scale...), then it would trigger something that would destroy all

Anyway... these examples are a little artificial, and somehow it makes me go back to questions of the 'Drake Equation' type, i.e. how likely is it that if we are _manifestly_ Turing-complete then we are _manifestly able to host self-replicators_

Anyway... these examples are a little artificial, and somehow it makes me go back to questions of the 'Drake Equation' type, i.e. how likely is it that if we are manifestly Turing-complete then we are manifestly able to host self-replicators

My guess is that the answer is _very likely_ (the probability of a real obstacle appearing is low... this intuition coming from the fact that I have a hard time coming up with an example)

My guess is that the answer is very likely (the probability of a real obstacle appearing is low... this intuition coming from the fact that I have a hard time coming up with an example)