Talk: Levin Hornischer (MCMP)

Title:

Universal Analog Computation: Fraïssé limits of dynamical systems

Abstract:

Analog computation is an alternative to digital computation, that has recently regained prominence, since it includes neural networks. Further important examples are cellular automata and differential analyzers. While analog computers offer many advantages, they lack a notion of universality akin to universal digital computers. Since analog computers are best formalized as dynamical systems, we review scattered results on universal dynamical systems, identifying four senses of universality. For nondeterministic systems, we construct a universal system as a Fraïssé limit. It not only is universal in many of the identified senses, it also is unique in also being homogeneous. For deterministic systems, a universal system cannot exist, but we provide a simple method to construct subclasses of deterministic systems with a universal system. This way, we introduce prosofic systems: those that are limits of sofic shifts, which play a central role in dynamical systems theory.