Compression-Based Analysis of Cyclic Tag System Emulated by Rule 110
Shingeru Ninagawa and Genaro J. Martinez
An elementary cellular automaton rule 110 supports universal computation by emulating cyclic tag system. We employ Lempel-Ziv (LZ) complexity as a measure of compressibility and calculate it during the cyclic tag system emulation process by rule 110. We observe the stepwise decline of LZ complexity during the process. That is caused by the conversion of appendants, symbols added onto the end of the tape, into moving data and the elimination of appendants. These phenomena occur if a cyclic tag system emulation process is solving a problem described by a recursive language.
Keywords: cyclic tag system, Lempel-Ziv complexity, rule