A Framework for Universality in Physics, Computer Science, and Beyond
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912011520049152 |
|---|---|
| author | Gonda, Tomáš Reinhart, Tobias Stengele, Sebastian Coves, Gemma De les |
| author_facet | Gonda, Tomáš Reinhart, Tobias Stengele, Sebastian Coves, Gemma De les |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_06851 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Framework for Universality in Physics, Computer Science, and Beyond Gonda, Tomáš Reinhart, Tobias Stengele, Sebastian Coves, Gemma De les Computational Complexity Formal Languages and Automata Theory Logic in Computer Science Mathematical Physics 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. |
| title | A Framework for Universality in Physics, Computer Science, and Beyond |
| topic | Computational Complexity Formal Languages and Automata Theory Logic in Computer Science Mathematical Physics |
| url | https://arxiv.org/abs/2307.06851 |