Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.)


share|improve this question
You should probably add a finite memory limitation. Otherwise the physical universe fails to be alive. –  Steve Huntsman Feb 28 '10 at 18:12
Maybe it is dead :) –  Anton Petrunin Feb 28 '10 at 18:50
See related MO question: mathoverflow.net/questions/15309, with links to references. –  Joel David Hamkins Mar 2 '10 at 14:24
add comment

3 Answers

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.

share|improve this answer
BUT, do I uderstand right that no one really was trying make a def in reasonable generality? --- If no I'm surprised. Even for CGL, there is a construction, but without such def it is not clear maybe such think can be done all the time... –  Anton Petrunin Mar 1 '10 at 18:19
Funny part --- it seems that shift space has subsystems which can compute, so maybe to produce right definition, one has to specify "right" subsystems. –  Anton Petrunin Mar 1 '10 at 18:22
I don't think your going-out-to-lunch criterion gets at the essence of computability. Imagine a computing device that ran programs as normal, but such that after a halt, the output was displayed only briefly, after which the device erased the output and embarked on meaningless complicated looping behavior. This would fail your going-out-lunch test, since you may miss the crucial moment, but most would still find a universal computer here. Rather, the essence of universal computation seems to be the ability to interpret any computation within the system, as I explain in my answer. –  Joel David Hamkins Mar 1 '10 at 21:02
@Joel: to made things more reasonable and not exotic: suppose Your system when finish computations ends with a loop when it prints infinite times just solution. Then You will have no halt moment at all, but also it will be infinite periodic behavior, so probably easily distinguishable; –  kakaz Mar 8 '10 at 17:25
add comment

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.

share|improve this answer
With this definition, can you prove say that shift space is dead? –  Anton Petrunin Feb 28 '10 at 22:07
One can think that in CGL you start with a random position with infinite set of points but you can change something in a bounded region. Then you can take any program for UTM and make it to work for arbitrary big number of steps. (by making free space around your "computer"). (So you do not need to choose exact point but can make it approximately). This way there is no real difference with shift space. –  Anton Petrunin Mar 1 '10 at 2:01
Shift space can not do "calculations". I think instead of "computable translation" one has to have an algorithm which makes "translation" in time depending only on n. –  Anton Petrunin Mar 1 '10 at 2:04
With that interpretation (and some minor assumptions on the interpretation functions), then the shift map is dead. I have edited my answer to explain this. –  Joel David Hamkins Mar 1 '10 at 13:39
"Church-Turing thesis, which seems fundamental to your question" - interesting part of it, is that it is empirical theorem about computable functions. So as it is used explicite in First Gödel Theorem of Incompleteness of arithmetic, it should be concerned to be in fact empirical fact and not mathematic theorem... That's way I suppose question asked here is important but should be reformulated: is for every system in mathematic to simulate it with Turing Machine. –  kakaz Mar 8 '10 at 17:30
add comment

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;-)

share|improve this answer
Main question is what do you mean by "embedding" Practically any dynamical system can be can be "embedded" (in some sense) in a shift space (and I do not want it to be "alive"). –  Anton Petrunin Feb 28 '10 at 20:34
I mean straight thing: to have subsystem which is equivalent (homeomorphic?) to some "minimal subset of PA". From my point of view interesting part is: what is "minimal subset of PA" which allows UTM construction. My intention was to check, if You have some model ( in fact some real mathematic system) what class of "reasonable theories" allow You to axiomatize it. But it seems to be too broad, exactly as in Your question;-) –  kakaz Feb 28 '10 at 21:58
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.