Consider the Game of Life. Given an infinite two-dimensional plane to run the Game on, and an infinite amount of "matter" so that one can give the automata any initial conditions one wishes, it is known that the Game of Life is Turing-complete, i.e. it can simulate anything number theory can.
The Game of Life has very simple rules - slightly more rigorously, its Kolmogorov complexity is low in most naive languages. Are there simpler (lower Kolmogorov complexity) Turing machines? Is it possible to prove that a Turing machine achieves the simplest possible construction in a given language?
A note - I'm only interested in the complexity of the rules required to run the code. An infinite number of states (or equivalently symbols) is fine, so long as the complexity of the map evaluated at each program step is low. (Game of Life is already down to three statements.)