The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.2 pp.415-422

- Publication Date
- 2019/02/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E102.A.415

- Type of Manuscript
- PAPER

- Category
- Nonlinear Problems

Shigeru NINAGAWA

Kanazawa Institute of Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Shigeru NINAGAWA, "Specific Properties of the Computation Process by a Turing Machine on the Game of Life" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 2, pp. 415-422, February 2019, doi: 10.1587/transfun.E102.A.415.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.415/_p

Copy

@ARTICLE{e102-a_2_415,

author={Shigeru NINAGAWA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Specific Properties of the Computation Process by a Turing Machine on the Game of Life},

year={2019},

volume={E102-A},

number={2},

pages={415-422},

abstract={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.},

keywords={},

doi={10.1587/transfun.E102.A.415},

ISSN={1745-1337},

month={February},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 415

EP - 422

AU - Shigeru NINAGAWA

PY - 2019

DO - 10.1587/transfun.E102.A.415

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E102-A

IS - 2

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - February 2019

AB - 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.

ER -