Notes on my thesis

(Added 23 Sep 2020) 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.

(Added 29 Apr 2022) Actually having read [Hurd] now, I no longer believe that it proves even the nonuniform result. The authors of [Culik-Pachl-Yu] seem to agree with [Hurd]'s proof of the nonuniform result, but their proof is completely independent from [Hurd] and I believe it is perfect.)

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: 29 Apr 2022