On self-replication and the halting problem

Hiroki Sayama, Department of Bioengineering Binghamton University, State University of New York

We aim to shed light on a fundamental relationship between living and computational systems by elucidating the close similarity of self-replication of von Neumann's universal constructors to circular computational processes of universal computers that appear in Turing's original proof of the undecidability of the halting problem. The result indicates the possibility of reinterpreting self-replicating organisms as attempting to solve the halting problem in the context of construction. This attempt will never be completed because of the undecidability of the problem, which may account for why life can maintain its reproductive activity for an indefinitely long period of time.