Sequentializing cellular automata

Publisher´s PDF
10.1007_s11047-019-09745-7.pdf - 597 KB
Lataukset121

Verkkojulkaisu

Tiivistelmä

We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.

item.page.okmtext