2009/01/25 by Bjørn Kjos-Hanssen, Kjos-Hanssen, Bjørn
Computer Science · #03D25 (Primary) #03D28 #06A12 #06A15 (Secondary) #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0901.3876
openalex publication_date 2009/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We characterize the isomorphism types of principal ideals of the Turing degrees below 0' that are lattices as the lattices with a Sigma-0-3 presentation, by showing that each Sigma-0-3 presentable bounded upper semilattice is isomorphic to such a principal ideal. We get a similar result for the Turing degrees below any degree above 0".