2024/08/29 by Tomáš Gonda, Tobias Reinhart, Sebastian Stengele +1 · 3 citations
Computer Science · Mathematics · #Algorithm #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computer science #Mathematics #Physics #Quantum Computing Algorithms and Architecture #Theoretical computer science #Turing #Turing machine #Universal Turing machine #Universality (dynamical systems)
paper · pdf · doi:10.46298/compositionality-6-3
published in Compositionality Volume 6 (2024)
openalex publication_date 2024/08/29 · rss pubdate 2024/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/21
Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.