Effective descriptive complexity of some compact sets
Investigating the descriptive complexity of sets has been a topic of theoretical computer science, particularly general recursion theory. In this paper, we investigate the effective descriptive complexity of certain sets of real numbers, namely, compact sets corresponding to a countable collection of closed intervals under the standard euclidian topology. We derive the result that the descriptive complexity of defining such sets is Π_1^1, which corresponds to the descriptive complexity of well-orderings. To prove such a result, we define several functions and relations that could be effectively computed by some abstract computing machine with access to pre-loaded infinite inputs.
Authors
- Alfonso B. Labao (ORCID: https://orcid.org/0000-0001-5321-377X)
Publication Details
- Journal
- SciEnggJ
- Published
- 2025-08-14
- DOI
- https://doi.org/10.54645/2025182oaz-78
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00