2024/10/21 by Takayuki Kihara, Kihara, Takayuki
Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #History and Theory of Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.2410.15795
openalex publication_date 2024/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this article, we investigate the arithmetical hierarchy from the perspective of realizability theory. An experimental observation in classical computability theory is that the notion of degrees of unsolvability for natural arithmetical decision problems only plays a role in counting the number of quantifiers, jumps, or mind-changes. In contrast, we reveal that when the realizability interpretation is combined with many-one reducibility, it becomes possible to classify natural arithmetical problems in a very nontrivial way.