On self-replication and the halting problem

Hiroki Sayama
Department of Bioengineering, Binghamton University, SUNY

     Full text: Not available
     Last modified: May 31, 2006

Abstract
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.