Notes on my thesis

I state in the thesis that [Hurd] from 1987 does not actually prove that limit sets of CA can be uncomputable, only that they are uniformly uncomputable. This is true, but it was observed already in 1989 by [Culik-Pachl-Yu] Culik II, Pachl, and Yu, who give a correct proof sketch.

References

[Hurd] Hurd, Lyman P. "Formal language characterizations of cellular automaton limit sets." Complex systems 1.1 (1987): 69-80.
[Culik-Pachl-Yu] Culik II, Karel, Jan Pachl, and Sheng Yu. "On the limit sets of cellular automata." SIAM Journal on Computing 18.4 (1989): 831-842


Last update: 23 Sep 2020