Analysis of Parity Problem by One-Dimensional Cellular Automaton

Shigeru NINAGAWA 

Publication
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)  Vol.J95-D  No.6  pp.1425-1428
Publication Date: 2012/06/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
Type of Manuscript: LETTER
Category: 
Keyword: 
cellular automaton,  rule 60,  parity problem,  cascade process,  LZ complexity, 

Full Text(in Japanese): PDF(344.8KB)

Summary: 
In this article we studied the behavior of elementary cellular automaton rule 60 solving the parity problem by measuring the Lempel-Ziv complexity. As a result, we found that the complexity of configuration decreases abruptly near the end of the computing process.