Stephen Wolfram recently introduced a prize, offering $30,000 for anyone who can make substantial progress on 3 problems he's posed relating to Rule 30. I've been obsessed with Cellular Automata (CA) and related machines for many years, so I though it was a good time to make a list of a few of the papers I've most enjoyed.
The last wolfram prize was concerned with proving the universality of a certain 2-state, 3-color turing machine. The prize was won by (undergraduate at the time) Alex Smith
The was some criticism of this result on FOM mailing list, due to the fact that Smith's machine requires the tape to be initialized with a particular non-periodic infinite string. It's hard to prove that this initial configuration isn't doing some of the work of the turing machine, and with only a finite piece of the string the automata only has the power of a Linear Bounded Automata.
Matthew Cook's papers proving the universality of the Rule 110 1D Cellular Automata:
Turlough Neary and Damian Woods have a great collection of papers on Small UTMs. The following gives small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4) based on emulating Rule 110.
On a different topic, this paper formalizes Wolfram's concept of CA Classes - Rule 30 is conjectured to belong to class 3 (effectively random), while Rule 110 belongs to class 4 (which includes all the turing-universal machines). Karel Culik and Sheng Yu develop some formalisations roughly equivalent to Wolfram's qualitative definitions and then show that the problem of deciding whether a give CA is a member of any of the classes is undecidable. This is a great example of how undecidability often gets in the way of proving anything in the general case when turing machines are involved.
Karel Culik II, Sheng Yu. (1988) Undecidability of CA Classification Schemes