Barbora Hudcová: Local Computational Universality Does Not Guarantee Self-Reproduction
Barbora Hudcová: Local Computational Universality Does Not Guarantee Self-Reproduction
On August 1, Michael Levin's academic media channel published a lecture by EPFL mathematician Barbora Hudcová on self-reproduction in cellular automata. In a preprint coauthored with Jordan Cotler and Clément Hongler, she describes a one-dimensional automaton that locally simulates a universal Turing machine but fails a necessary condition for nontrivial self-reproduction.
A quine is a program that prints its own source code. In John von Neumann's scheme, the description serves two purposes. It first acts as a blueprint for construction, and is then copied into the offspring. The offspring receives both the instructions and the mechanism that reads them and continues the process.
A cellular automaton is a grid of cells, each of which changes state according to a rule based on the states of its neighbors. A region of this grid can be configured to simulate, step by step, a universal Turing machine, an abstract computing device that operates on symbols written on a tape. Local universality means that this simulation can be contained within a finite region of the grid.
Cotler, Hongler, and Hudcová constructed a one-dimensional automaton with this property. Their necessary condition for self-reproduction requires the automaton's dynamics to recreate a functioning structure, not merely to perform a computation. The ability to execute any program therefore does not explain how a system will assemble an offspring, pass the description to it, and initiate another cycle.
In the authors' formal model, globally universal automata belong to the class of universal self-replicators, which in turn belongs to the class of locally universal automata. For a robot, a self-replicating laboratory, or a digital model of a person, this hierarchy provides a specific test: whether the offspring has instructions, a mechanism for reading them, and the ability to repeat the assembly process.