It seems like our physics has a few fundamental characteristics that change the flavor of the question:
Reversibility. This implies that the task must be impossible on average—you can only succeed under some assumption about the environment (e.g. sparsity).
Conservation of energy/mass/momentum (which seem fundamental to the way we build and defend structures in our world).
I think this is an interesting question, but if poking around it would probably be nicer to work with simple rules that share (at least) these features of physics.
The reversibility seems especially important to me. In some fundamental sense our universe doesn’t actually allow an AI (or human) no matter how intelligent to bring the universe into a controlled state. The reversibility gives us a thermodynamics such that in order to bring any part of the world from an unknown state to a known state we have to scramble something we did know back to a state of unknowing.
So, in our universe, the AI needs access to fuel (negative entropy) at least up to the task it is set. (Of course it can find fuel out their in its environment, but everything it finds can either be fuel, or can be canvas for its creation. But at least usually it cannot be both. Because the fuel needs to be randomised (essentially serve as a dump for entropy), while the canvas needs to be un-randomised.
Yeah I agree. There was a bit of discussion re conservation of energy here too. I do like thought experiments in cellular automata because of the spatially localized nature of the transition function, which matches our physics. Do you have any suggestions for automata that also have reversibility and conservation of energy?
That seems great. Is there any reason people talk a lot about Life instead of Critters?
(Seems like Critters also supports universal computers and many other kinds of machines. Are there any respects in which it is known to be less rich than Life?)
You’re probably right, but I can think of the following points.
Its rule is more complicated than Life’s, so its worse as an example of emergent complexity from simple rules (which was Conway’s original motivation).
It’s also a harder location to demonstrate self replication. Any self replicator in Critters would have to be fed with some food source.
I feel like they must exist (and there may not be that many simple nice ones). I expect someone who knows more physics could design them more easily.
My best guess would be to get both properties by defining the system via some kind of discrete hamiltonian. I don’t know how that works, i.e. if there is a way of making the hamiltonian discrete (in time and in values of the CA) that still gives you both properties and is generally nice. I would guess there is and that people have written papers about it. But it also seems like that could easily fail in one way or another.
It’s surprisingly non-trivial to find that by googling though I didn’t try very hard. May look a bit more tonight (or think about it a bit since it seems fun). Finding a suitable replacement for the game of life that has good conservation laws + reversibility (while still having a similar level of richness) would be nice.
I guess the important part of the hamiltonian construction may be just having the next state depend on x(t) and x(t-1) (apparently those are called second-order cellular automata). Once you do that it’s relatively easy to make them reversible, you just need the dependence of x(t+1) on x(t-1) to be a permutation. But I don’t know whether using finite differences for the hamiltonian will easily give you conservation of momentum + energy in the same way that it would with derivatives.
I have never thought much about reversibility. Do humans make heavy use of reversible processes? And what is the relation between cross entropy and reversibility?
I don’t know if GR or some cosmological thing (inflation) breaks reversibility. But classical and quantum mechanics are both reversible. So I would say that all of the lowest-level processes used by human beings are reversible. (Although of course thermodynamics does the normal counter-intuitive thing where the reversibility of the underlying steps is the reason why the overall process is, for all practical purposes, irreversible.)
It seems like our physics has a few fundamental characteristics that change the flavor of the question:
Reversibility. This implies that the task must be impossible on average—you can only succeed under some assumption about the environment (e.g. sparsity).
Conservation of energy/mass/momentum (which seem fundamental to the way we build and defend structures in our world).
I think this is an interesting question, but if poking around it would probably be nicer to work with simple rules that share (at least) these features of physics.
The reversibility seems especially important to me. In some fundamental sense our universe doesn’t actually allow an AI (or human) no matter how intelligent to bring the universe into a controlled state. The reversibility gives us a thermodynamics such that in order to bring any part of the world from an unknown state to a known state we have to scramble something we did know back to a state of unknowing.
So, in our universe, the AI needs access to fuel (negative entropy) at least up to the task it is set. (Of course it can find fuel out their in its environment, but everything it finds can either be fuel, or can be canvas for its creation. But at least usually it cannot be both. Because the fuel needs to be randomised (essentially serve as a dump for entropy), while the canvas needs to be un-randomised.
Yeah I agree. There was a bit of discussion re conservation of energy here too. I do like thought experiments in cellular automata because of the spatially localized nature of the transition function, which matches our physics. Do you have any suggestions for automata that also have reversibility and conservation of energy?
https://en.wikipedia.org/wiki/Critters_(cellular_automaton)
That seems great. Is there any reason people talk a lot about Life instead of Critters?
(Seems like Critters also supports universal computers and many other kinds of machines. Are there any respects in which it is known to be less rich than Life?)
You’re probably right, but I can think of the following points.
Its rule is more complicated than Life’s, so its worse as an example of emergent complexity from simple rules (which was Conway’s original motivation).
It’s also a harder location to demonstrate self replication. Any self replicator in Critters would have to be fed with some food source.
I feel like they must exist (and there may not be that many simple nice ones). I expect someone who knows more physics could design them more easily.
My best guess would be to get both properties by defining the system via some kind of discrete hamiltonian. I don’t know how that works, i.e. if there is a way of making the hamiltonian discrete (in time and in values of the CA) that still gives you both properties and is generally nice. I would guess there is and that people have written papers about it. But it also seems like that could easily fail in one way or another.
It’s surprisingly non-trivial to find that by googling though I didn’t try very hard. May look a bit more tonight (or think about it a bit since it seems fun). Finding a suitable replacement for the game of life that has good conservation laws + reversibility (while still having a similar level of richness) would be nice.
I guess the important part of the hamiltonian construction may be just having the next state depend on x(t) and x(t-1) (apparently those are called second-order cellular automata). Once you do that it’s relatively easy to make them reversible, you just need the dependence of x(t+1) on x(t-1) to be a permutation. But I don’t know whether using finite differences for the hamiltonian will easily give you conservation of momentum + energy in the same way that it would with derivatives.
I have never thought much about reversibility. Do humans make heavy use of reversible processes? And what is the relation between cross entropy and reversibility?
I don’t know if GR or some cosmological thing (inflation) breaks reversibility. But classical and quantum mechanics are both reversible. So I would say that all of the lowest-level processes used by human beings are reversible. (Although of course thermodynamics does the normal counter-intuitive thing where the reversibility of the underlying steps is the reason why the overall process is, for all practical purposes, irreversible.)
This paper looks at mutual information (which I think relates to the cross entropy you mention), and how it connects to reversibility and entropy. https://bayes.wustl.edu/etj/articles/gibbs.vs.boltzmann.pdf
(Aside, their is no way that whoever maintains the website hosting that paper and the LW community don’t overlap. The mutual information is too high.)