Computable classifications of continuous, transducer, and regular functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915133240901632 |
|---|---|
| author | Franklin, Johanna N. Y. Hölzl, Rupert Melnikov, Alexander Ng, Keng Meng Turetsky, Daniel |
| author_facet | Franklin, Johanna N. Y. Hölzl, Rupert Melnikov, Alexander Ng, Keng Meng Turetsky, Daniel |
| contents | We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipschitz functions is $Σ^0_2$-complete. (Every regular function is pointwise linear-time Lipschitz.) We show that a function $f\colon [0,1] \rightarrow \mathbb{R}$ is (binary) transducer if and only if it is continuous regular. As one of many consequences, our $Σ^0_2$-completeness result covers the class of transducer functions as well. Finally, we show that the Banach space $C[0,1]$ of real-valued continuous functions admits an arithmetical classification among separable Banach spaces. Our proofs combine methods of abstract computability theory, automata theory, and functional analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2010_09499 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Computable classifications of continuous, transducer, and regular functions Franklin, Johanna N. Y. Hölzl, Rupert Melnikov, Alexander Ng, Keng Meng Turetsky, Daniel Logic We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipschitz functions is $Σ^0_2$-complete. (Every regular function is pointwise linear-time Lipschitz.) We show that a function $f\colon [0,1] \rightarrow \mathbb{R}$ is (binary) transducer if and only if it is continuous regular. As one of many consequences, our $Σ^0_2$-completeness result covers the class of transducer functions as well. Finally, we show that the Banach space $C[0,1]$ of real-valued continuous functions admits an arithmetical classification among separable Banach spaces. Our proofs combine methods of abstract computability theory, automata theory, and functional analysis. |
| title | Computable classifications of continuous, transducer, and regular functions |
| topic | Logic |
| url | https://arxiv.org/abs/2010.09499 |