Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2010.09499 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.