We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Construction theory, self-replication, and the halting problem.
- Authors
Sayama, Hiroki
- 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
- Publication
Complexity, 2008, Vol 13, Issue 5, p16
- ISSN
1076-2787
- Publication type
Article
- DOI
10.1002/cplx.20218