Hydrodynamic and symbolic models of computation with advice
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929516341886976 |
|---|---|
| author | Cardona, Robert |
| author_facet | Cardona, Robert |
| contents | Dynamical systems and physical models defined on idealized continuous phase spaces are known to exhibit non-computable phenomena, examples include the wave equation, recurrent neural networks, or Julia sets in holomorphic dynamics. Inspired by the works of Moore and Siegelmann, we show that ideal fluids, modeled by the Euler equations, are capable of simulating poly-time Turing machines with polynomial advice on compact three-dimensional domains. This is precisely the complexity class $P/poly$ considered by Siegelmann in her study of analog recurrent neural networks. In addition, we introduce a new class of symbolic systems, related to countably piecewise linear transformations of the unit square, that is capable of simulating Turing machines with advice in real-time, contrary to previously known models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_11820 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hydrodynamic and symbolic models of computation with advice Cardona, Robert Mathematical Physics Computational Complexity Dynamical Systems Dynamical systems and physical models defined on idealized continuous phase spaces are known to exhibit non-computable phenomena, examples include the wave equation, recurrent neural networks, or Julia sets in holomorphic dynamics. Inspired by the works of Moore and Siegelmann, we show that ideal fluids, modeled by the Euler equations, are capable of simulating poly-time Turing machines with polynomial advice on compact three-dimensional domains. This is precisely the complexity class $P/poly$ considered by Siegelmann in her study of analog recurrent neural networks. In addition, we introduce a new class of symbolic systems, related to countably piecewise linear transformations of the unit square, that is capable of simulating Turing machines with advice in real-time, contrary to previously known models. |
| title | Hydrodynamic and symbolic models of computation with advice |
| topic | Mathematical Physics Computational Complexity Dynamical Systems |
| url | https://arxiv.org/abs/2301.11820 |