
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

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.E102A
No.2
pp.415422 Publication Date: 2019/02/01
Online ISSN: 17451337
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 twodimensional 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.

