For references, there is a huge literature on the Church-Turing thesis, which seems fundamental to your question. (Follow the link for a big list of references.) Mathematicians and philosophers have grappled with various aspects of what it means to find a universal computer within a system. See also Copeland's article on the Church-Turing thesis, which also has an extensive list of references.
To find a universal computer in any system, one needs to be able to set up an initial configuration corresponding to a given program and input, let the system evolve, and then be able both to recognize when the system has reached a conclusion for the computation and interpret the result.
The game of life exhibits this phenomenon. For any Turing
machine program p and input n, there is an initial
configuration of a game of life, such that as that
configuration evolves according to the rules of GOL, the
configurations can be viewed as simulating the Turing
machine computation. A halting computation leads to a
recognizable feature in the GOL configuration, and when
this feature occurs, the output of the computation can be
read from that configuration.
Abstractly, we can say that a function f from a set C to itself, viewed as a dynamical system in the sense that we intend to iterate f, is alive if there is a "set-up" function s, a termination set T and an output interpretation function t, such that a program p on input n gives output m if and only if when we compute the iterates fk(s(p,n)), then for the least k for which this value is in T, the output t(fk(s(p,n))) = m. That is, we set up the system, let it run freely, and if and when it is finished, we interpret the output correctly.
You will want to insist that f, s, and T are computable (and quickly computable) in a sense that is acceptable to you, for otherwise there will be too much computation occurring within the set-up or within the output interpretation. (This was the basis of your and Gowers's objections to my previous account of the shift map.)
On this account, all the usual models of computability are alive. For example, the computation of register machines, Turing machines themselves, flowchart machines, automata with stacks and so on, for all the usual Church-Turing complete accounts of computability. These can all be viewed as dynamical systems in the sense thtat the computation proceeds by iterating a relatively trivial update function, corresponding to one step of computation. The game of life, also, is alive.
The shift map, of course, acts naturally on infinite objects, which can have a huge amount of information, which the shift map brings into view.
Nevertheless, by imposing natural requirements on s, t and T, one can see that the shift map is dead. You proposed that, given (p,n), we should set up an initial configuration that modifies a random background sequence only finitely, and then run the shift map.
Let us also assume that s, t and T are computable, and also that T and t do not depend on p or n. (That is, that in order to interpret the output, we do not need to know what the program or input was.) In this case, there will be no universal computer. The reason is that if the computation halts before the length of the modifications made by the set-up, then there is a computable bound on the length of the computation, and if it halts after, then all information about n is completely lost, and the function must be constant on inputs leading to this situation. Thus, we will be able to computably solve the halting problem for the functions implemented by the shift map, and there can be no universal computer here.
If one is more relaxed about the requirements on s, t and T, however, then one can still find a universal computer here. Let us only change the requirement that t and T not depend on p and n. In this case, we don't need any set-up at all. Let us interpret "random" as meaning that all finite substrings occur in the background sequence. Now, if the computation of p on input n halts, then there will be a substring occuring in the background sequence that corresponds to coding exactly this computation, set off between two markers. Let T be the set of infinite strings such that between the first two markers on it, there is a string coding the entire computation of p on input n. Let t be the function mapping this coded computation to its output. This system is alive in the technical sense I gave, and the way that it works is by using the ambient randomness of the background sequence you provided to verify that a given computation proceeds correctly. This kind of computability resembles the DNA model of computing, where one has a beaker full of random DNA molecules which combine and reassemble according to chemical rules. (For the traveling salesman problem, imagine that DNA strands corresponding to less optimal paths are destroyed and those with more optimal paths are reproduced.) The shift map and output interpretation are like the filter that sorts through the beaker looking for the desired answer.
