Construction theory, self-replication, and the halting problem

✍ Scribed by Hiroki Sayama

• Book ID: 102123392
• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 188 KB
• Volume: 13
• Category: Article
• ISSN: 1076-2787
• DOI: 10.1002/cplx.20218

✦ Synopsis

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