2013/08/29 by André Nies, Nies, Andre
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1308.6399
openalex publication_date 2013/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A major part of computability theory focuses on the analysis of a few structures of central importance. As a tool, the method of coding with first-order formulas has been applied with great success. For instance, in the c.e. Turing degrees, it has been used to determine the complexity of the elementary theory, to provide restrictions on automorphisms, and even to obtain definability results (work of Harrington, Nies, Shore, Slaman, and others). We describe how a similar program can be carried out for several other structures, including the structure of c.e. many one degrees, the structure of c.e. weak truth table degrees and the lattice of c.e. sets under inclusion. In all cases we will obtain undecidability of, or even an interpretation of true arithmetic in the theory of the structure. For the c.e. many one-degrees, we also obtain definability results and restrictions on automorphisms. This work appeared first as the author's habilitation thesis at the Universitaet Heidelberg, 1998.