A Framework for Universality in Physics, Computer Science, and Beyond
arXiv:2307.06851 · doi:10.46298/compositionality-6-3
Abstract
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.
66 pages, 12 figures, many diagrams. v3: DOI changed
References in corpus (17)
- A mathematical theory of resources
- Restriction categories III: colimits, partial limits, and extensivity
- A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics
- Universal Quantum Hamiltonians
- A Convenient Category for Higher-Order Probability Theory
- A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points
- Categories for the practising physicist
- Cartesian Bicategories II
- Monotones in General Resource Theories
- Free gs-monoidal categories and free Markov categories
- Notes on Category Theory with examples from basic mathematics
- An Introduction to String Diagrams for Computer Scientists
- Classical spin Hamiltonians are context-sensitive languages
- Substructural fixed-point theorems and the diagonal argument: theme and variations
- Absolute continuity, supports and idempotent splitting in categorical probability
- Programs as Diagrams: From Categorical Computability to Computable Categories
- From Gs-monoidal to Oplax Cartesian Categories: Constructions and Functorial Completeness