[niederman]

I suspect this proof could be greatly simplified by the use of tag systems (https://en.m.wikipedia.org/wiki/Tag_system) rather than cellular automata.