Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 23-35 |
| Number of pages | 13 |
| Journal | Journal of Cellular Automata |
| Volume | 9 |
| Issue number | 1 |
| State | Published - 2014 |
Keywords
- Cyclic tag system
- Lempel-Ziv complexity
- Rule 110