Specific Properties of the Computation Process by a Turing Machine on the Game of Life

Shigeru NINAGAWA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.2   pp.415-422
Publication Date: 2019/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.415
Type of Manuscript: PAPER
Category: Nonlinear Problems
Keyword: 
Game of Life,  computational universality,  turing machine,  spectral analysis,  Lyapunov exponent,  

Full Text: PDF(1.5MB)
>>Buy this Article


Summary: 
The Game of Life, a two-dimensional computationally universal cellular automaton, is known to exhibits 1/f noise in the evolutions starting from random configurations. In this paper we perform the spectral analysis on the computation process by a Turing machine constructed on the array of the Game of Life. As a result, the power spectrum averaged over the whole array has almost flat line at low frequencies and a lot of sharp peaks at high frequencies although some regions in which complicated behavior such as frequent memory rewriting occurs exhibit 1/f noise. This singular power spectrum is, however, easily turned into 1/f by slightly deforming the initial configuration of the Turing machine. These results emphasize the peculiarity of the computation process on the Game of Life that is never shared with the evolutions from random configurations. The Lyapunov exponents have positive values in three out of six trials and zero or negative values in other three trails. That means the computation process is essentially chaotic but it has capable of recovering a slight error in the configuration of the Turing machine.