Search
Search Results
-
Categoricity Spectra of Computable Structures
The categoricity spectrum of a computable structure S is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable...
-
Degree Spectra of Structures
In this survey, we discuss computability spectra of countable structures that provide a natural measure of non-computability of a structure. This...
-
Precomplete Numberings
In this survey, we discuss the theory of precomplete numberings, which appear frequently in computability theory. Precomplete numberings are closely...
-
Computable Presentability of Countable Linear Orders
The main goal of this paper is to study algorithmic properties of countable linear orders by constructing effective presentations of these structures...
-
Computable Linear Orders and Limitwise Monotonic Functions
In this paper, we describe the technique of extremely monotonic functions in the theory of computable linear orders. The basic definitions of...
-
Turing Computability: Structural Theory
In this work, we review results of the last years related to the development of the structural theory of n -c.e. Turing degrees for n > 1. We also...
-
Degrees of bi-embeddable categoricity of equivalence structures
We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable...
-
Computable valued fields
We investigate the computability-theoretic properties of valued fields, and in particular algebraically closed valued fields and p -adically closed...
-
Scott sentences for certain groups
We give Scott sentences for certain computable groups, and we use index set calculations as a way of checking that our Scott sentences are as simple...
-
Computable dimension for ordered fields
The computable dimension of a structure counts the number of computable copies up to computable isomorphism. In this paper, we consider the possible...
-
Degree spectra of the successor relation of computable linear orderings
We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum...
-
Chains and antichains in partial orderings
We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which...
-
Linear orders with distinguished function symbol
We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably...
-
Space complexity of Abelian groups
We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We...