Alive dynamical system Intuitively, one can say that a dynamical system is alive if one can build a universal Turing machine inside.
So, Conway's Game of Life is alive and shift space should be dead.
I fail to make this definition precise. 
Please let me know if someone made it (or at least was trying to).
(It is  nice if you can make a def. 
BUT I'm mostly interested if you saw such definition in the literature.)
Comments:


*

*There is a relateted question, and it links to this paper by Graça--Campagnolo--Buescu (thanks to Joel).

 A: 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.
A: I don't pretend to have an answer to this question, but let me at least try (informally and tentatively) to clarify the distinction. Suppose I have a computational problem and I want to solve it. I also happen to have the Game of Life handy, and plenty of information about it. What I presume the usual statement about the Game of Life encoding a universal Turing machine is that there is some algorithmic way of translating my algorithm (for finding a matching in a bipartite graph, say) into an initial configuration for the Game of Life such that after a certain time I can look at the output and see whether a certain position has a + or a -, and that will agree with what the algorithm gives.
Now suppose that I am presented with the shift space. This time, I run the entire computation, describe this run somehow as a sequence of 0s and 1s, and then apply the shift map repeatedly to the resulting sequence. But what have I gained from applying the shift map? Precisely nothing, because in order to work out the sequence I had to run the entire computation. 
Here perhaps is a genuine difference between the two. Suppose I have a program and I don't know whether it halts, and would like to find out. With the Game of Life, after a finite time I can translate the program into an initial configuration, and there can be some stopping rule, and then I can go off and have lunch and leave the Game of Life chugging away. With the shift space, if it happens that the program doesn't halt, I will never finish the process of creating a sequence on which the shift should act.
A: To build UTM is equivalent to define inside recurrence functions space -  which consists of certain relations inside or homomorphic to it (or to define typed lambda calculus). So it seems to be natural to require to embed such "subsystem" inside dynamical system in order to call it as You say Alive. To define full class of recurrence function is enough to have for example Peano Arithmetic inside but it seems to much more than minimal requirement. From Robinson Arithmetic article from Wikipedia:  

"Robinson (1950) derived the Q axioms
  (1)-(7) above by noting just what PA
  axioms are required to prove
  (Mendelson 1997: Th. 3.24) that every
  computable function is representable
  in PA."


It seems that You question is close related ( in spirit) to my question here: Given is "model". How many theories may it be a model? I was asking for information which theories are satisfied in given model ( given model is model for which theories). It looks like You are asking for "dynamical systems" which allows You to embed model of Universal Turing Machine, or model of lambda calculus, or model of recurrence functions. It is somehow connected in weak manner.

Another interesting matter is any intuition within Your question. What do You mean by "alive" beside that UTM machine is representable within such system? Take into account that from equivalence of several known "models of computation" You cannot follow that this models are the only possible. This is only an example of incomplete induction within mathematic ( Church-Turing Thesis mentioned somewhere here). You ask for exactly UTM machine inside system or You are looking for something "more exotic"? I ask because to use word "alive" is very strange in such context. To live is in known meaning, completely nonequivalent to: "be UTM" or "be simulated by UTN". It is strange to use such word.

Is it the case that UTM may simulate shift space? So in fact if You are able to implement UTM inside You also can shift space? It looks like it is possible at least with TM with two tapes. Then maybe You should look for "dead space" definition and not "alive" one;-)
