On self-replication and the halting problem
Department of Bioengineering, Binghamton University, SUNY
Last modified: May 31, 2006
I will elucidate a close similarity in formulation between self-replication of von Neumann's universal constructors and circular computational processes of universal computers that appear in Turing's original proof of the undecidability of the halting problem. The result indicates a possibility of reinterpreting self-replicating living systems as attemping to solve the undecidable halting problem in the context of construction.