Algorithmical Unsolvability of the Ergodicity Problem for Binary Cellular Automata

A. Toom

2000, v.6, Issue 4, 569-577


We prove the algorithmical unsolvability of the ergodicity problem for a class of one-dimensional translation-invariant cellular automata with two states, all transition probabilities being in {0,1/2,1}, and a similar statement for a finite space.

Keywords: random processes,local interaction,cellular automata,ergodicity,unsolvability,Turing machine


Please log in or register to leave a comment

There are no comments yet