Kolmogorov Complexity and the Garden of Eden Theorem

Andrey Alpeev

Suppose $\tau$ is a cellular automaton over an amenable group and a finite alphabet. Celebrated Garden of Eden theorem states, that pre-injectivity of $\tau$ is equivalent to non-existen…