International Symposium on Nonlinear Theory and its Applications


Session Number:C3L-B



Isle of Eden in 1D binary cellular automaton as a manifestation of Godel incompleteness and a proposal for a ridge between analytical results and spatial-temporal logic patterns

Tamas Roska,  


Publication Date:2010/9/5

Online ISSN:2188-5079


PDF download (106.3KB)

The richness of spatial-temporal dynamics is known since the Morphogenesis paper of Turing [1] and the introduction of the Cellular Automaton by Von Neumann and Ulam [2]. The recent book of S. Wolfram [3] showcases, by a wealth of examples and one theorem (rule 110), the richness of the simplest spatial temporal binary patterns in the one dimensional (1D) binary cellular automaton, a special case of standard CNN Dynamics [8]. The rigorous study of this model by L. O. Chua and others [4] led to a surprisingly simple and deep insight in the qualitative behavior of these models. The existence of the so called Isle of Eden, a sequence of states without predecessors and successors, is one interesting phenomenon. The aim of this paper is twofold. (i) We show that the Isle of Eden is a simple manifestation of Godel’s incompleteness theorem by using the way of the original proof of Godel. (ii) We propose a way to generate results on binary spatial-temporal logic patterns via analytical proofs using the binary to continuous transformation introduced by L. O. Chua et. al. [4]. We note that the 1D Cellular Automaton is a simple case of a CNN dynamics programmably embedded in a CNN Universal Machine [5] and it could be simply implemented on existing cellular camera computers [6], as well as on different cellular many-core chips like FPGAs.