2025/10/11 by Levin Hornischer, Hornischer, Levin
Biochemistry, Genetics and Molecular Biology · Computer Science · #03C30 #37B10 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #DNA and Biological Computing #Dynamical Systems (math.DS) #FOS: Mathematics #Primary 68Q09 #secondary 18A35
paper · pdf · doi:10.48550/arxiv.2510.10184
openalex publication_date 2025/10/11 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28
Analog computation is an alternative to digital computation, that has recently re-gained prominence, since it includes neural networks and neuromorphic computing. 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. We identify four senses of universality and connect to the two main general theories of computation: coalgebra and domain theory. 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 additionally being homogeneous. For deterministic systems, a universal system cannot exist, but we provide a simple method for constructing subclasses of deterministic systems with a universal and homogeneous system. This way, we introduce sofic proshifts: those systems that are limits of sofic shifts. In fact, their universal and homogeneous system even is a limit of shifts of finite type and has the shadowing property.