Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.19304 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913373055090688 |
|---|---|
| author | Gozzi, Riccardo Bournez, Olivier |
| author_facet | Gozzi, Riccardo Bournez, Olivier |
| contents | In a recent article, we introduced and studied a precise class of dynamical systems called solvable systems. These systems present a dynamic ruled by discontinuous ordinary differential equations with solvable right-hand terms and unique evolution. They correspond to a class of systems for which a transfinite method exist to compute the solution. We also presented several examples including a nontrivial one whose solution yields, at an integer time, a real encoding of the halting set for Turing machines; therefore showcasing that the behavior of solvable systems might describe ordinal Turing computations. In the current article, we study in more depth solvable systems, using tools from descriptive set theory. By establishing a correspondence with the class of well-founded trees, we construct a coanalytic ranking over the set of solvable functions and discuss its relation with other existing rankings for differentiable functions, in particular with the Kechris-Woodin, Denjoy and Zalcwasser ranking. We prove that our ranking is unbounded below the first uncountable ordinal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19304 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Set Descriptive Complexity of Solvable Functions Gozzi, Riccardo Bournez, Olivier Computational Complexity Logic in Computer Science Dynamical Systems In a recent article, we introduced and studied a precise class of dynamical systems called solvable systems. These systems present a dynamic ruled by discontinuous ordinary differential equations with solvable right-hand terms and unique evolution. They correspond to a class of systems for which a transfinite method exist to compute the solution. We also presented several examples including a nontrivial one whose solution yields, at an integer time, a real encoding of the halting set for Turing machines; therefore showcasing that the behavior of solvable systems might describe ordinal Turing computations. In the current article, we study in more depth solvable systems, using tools from descriptive set theory. By establishing a correspondence with the class of well-founded trees, we construct a coanalytic ranking over the set of solvable functions and discuss its relation with other existing rankings for differentiable functions, in particular with the Kechris-Woodin, Denjoy and Zalcwasser ranking. We prove that our ranking is unbounded below the first uncountable ordinal. |
| title | Set Descriptive Complexity of Solvable Functions |
| topic | Computational Complexity Logic in Computer Science Dynamical Systems |
| url | https://arxiv.org/abs/2405.19304 |