Tomáš Gonda ; Tobias Reinhart ; Sebastian Stengele ; Gemma De les Coves - A Framework for Universality in Physics, Computer Science, and Beyond

compositionality:14134 - Compositionality, August 29, 2024, Volume 6 (2024) - https://doi.org/10.46298/compositionality-6-3
A Framework for Universality in Physics, Computer Science, and BeyondArticle

Authors: Tomáš Gonda 1; Tobias Reinhart 1; Sebastian Stengele 2; Gemma De les Coves 1

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.


Volume: Volume 6 (2024)
Published on: August 29, 2024
Imported on: August 29, 2024
Keywords: Computer Science - Computational Complexity,Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science,Mathematical Physics

Consultation statistics

This page has been seen 579 times.
This article's PDF has been downloaded 261 times.