Artificial Life VI


Self-organized Complexity in Computer Program Ecosystem

Shinichiro Yoshii
Complex Systems, Hokkaido University
http://junji.complex.eng.hokudai.ac.jp/export/yoshii/WWW/index.html

Satoshi Ohashi
Complex Systems, Hokkaido University

Yukinori Kakazu
Complex Systems, Hokkaido University


Abstract

This paper is concerned with self-organization of computational procedures, namely, algorithms or computer programs. Self-organizational behaviors of physical systems have been elucidated through theoretical studies. In the realm of artificial life, some simulations have been aimed at demonstrating self-organization of genetic information, for example. On the other hand, we are interested in how an abstract concept of computation may be able to self-organize. Furthermore, another issue of this paper is what kind of model should be used for simulating such an interest. Because the notion of computation itself being abstract is yet very strict and universal, utilization of a simulation model without arbitrariness of a designer is necessary to discuss that. This paper proposes an ecological model consisting of computer programs described by Turing machine. Turing machine is equivalent in computing power to the digital computer as we know it, and also to most general mathematical models of computation. In our model, these Turing machines interact with each other by reading the other machines' descriptions as an input tape. We believe that emergent computing in the next generation needs to explore the evolution of information architecture, that is, the computer program itself. This paper demonstrates that self-assembling networks of computer programs emerge in the interacting dynamics of the proposed ecosystem. Furthermore, this paper discusses that, with regard to the computational complexity, there is an upper limit provided in the initial configuration, and the computer programs self-organize toward the invisible attractor.


Back to ALife6 Table of Contents / Keyword Index / Author Index / Meeting Schedule