Universal computation and asymptotic behaviour in symbolic dynamics.
Time: 14:30 -- Location: LIX
Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding to the implementation of an arbitrary program, depend on the problem being considered. This approach contrasts with the naive idea of a "generalist" Turing-universality that would make all relevant problems undecidable.
In this talk, I will present two discrete dynamical systems where various ways to implement universal computation have been considered: cellular automata and Langton's ant. In cellular automata, we proved that predicting the typical asymptotic behaviour from a random initial configuration is undecidable in the general case. I will compare the constructions involved in this proof with other ways to simulate universal computation in cellular automata. Most notably, these constructions imply the indecidability of different classes of problems and behave differently under dynamical restrictions. In Langton's ant, I will present ongoing work that attempts to connect the computational complexity of the ant's trajectory with its ability to simulate universal computation in various forms.