Construction theory, self‐replication, and the halting problem
Hiroki Sayama · Complexity · 2008
Abstract This essay aims to propose construction theory, a new domain of theoretical research on machine construction, and use it to shed light on a fundamental relationship between living and computational systems. Specifically, we argue that self‐replication of von Neumann's universal constructors holds a close similarity 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 a self‐replicating biological organism as embodying an attempt to solve the halting problem for a diagonal input in the context of construction. This attempt will never be completed because of the indefinite cascade of self‐computation/construction, which accounts for the undecidability of the halting problem and also agrees well with the fact that life has maintained its reproductive activity for an indefinitely long period of time. © 2008 Wiley Periodicals, Inc. Complexity, 2008