Universit e catholique de Louvain

namical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines and tag systems, our definition coincides with the classical definition. It yields, however, a new definition for cellular automata and subshifts. Our definition is robust with respect to perturbations on the initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have an infinite number of subsystems. We also discuss the idea according to which computation should occur at the `edge of chaos' and we exhibit a universal chaotic system. ii Chapter 5: Complexity of control on finite automata. We consider control questions for input-output automata. In particular, we find estimations of the minimal number of states of an automaton able to contr