We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the Σβ hierarchy. We focus on linear orderings. We show that at the Σ1 level, all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the Σα+2 level for any α∈ω1CK the set of linear orderings with generically or coarsely computable copies is Σ11-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results, we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy.

Abstract We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

Abstract We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$ , using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Montalbán. This proof allows the possibility that the elements of F are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of F represented by triples in $H(F)$ . Looking at what was used to arrive at this parameter-free interpretation of F in $H(F)$ , we give general conditions sufficient to eliminate parameters from interpretations.

Abstract In recent years, computability theorists have extensively studied generically and coarsely computable sets. This study of approximate computability was originally motivated by asymptotic density problems in combinatorial group theory. We generalize the notions of generic and coarse computability of sets, introduced by Jockusch and Schupp, to arbitrary structures by defining generically and coarsely computable and computably enumerable structures. There are two directions in which these notions could potentially trivialize: either all structures could have a densely computable copy or only those having a computable (or computably enumerable) copy. We show that some particular classes of structures realize each of these extremal conditions, while other classes realize neither of them. To further explore these concepts, we introduce a graded family of elementarity conditions for substructures, in which we require that the dense sets under consideration be ‘strong’ substructures of the original structure. Here, again, for a given class, the notion could trivialize in the same two directions and we show that both are possible. For each class that we investigate, there is some natural number $n$ such that requiring $\varSigma _{n}$ elementarity of substructures is enough to trivialize the class of generically or densely computable structures, witnessing the essentially structural character of these notions.

We say that a structure $\mathcal{A}$ admits \emph{strong jump inversion} provided that for every oracle $X$, if $X'$ computes $D(\mathcal{C})'$ for some $\mathcal{C}\cong\mathcal{A}$, then $X$ computes $D(\mathcal{B})$ for some $\mathcal{B}\cong\mathcal{A}$. Jockusch and Soare \cite{JS} showed that there are low linear orderings without computable copies, but Downey and Jockusch \cite{DJ} showed that every Boolean algebra admits strong jump inversion. More recently, D.\ Marker and R.\ Miller \cite{MM} have shown that all countable models of $DCF_0$ (the theory of differentially closed fields of characteristic $0$) admit strong jump inversion. We establish a general result with sufficient conditions for a structure $\mathcal{A}$ to admit strong jump inversion. Our conditions involve an enumeration of $B_1$-types, where these are made up of formulas that are Boolean combinations of existential formulas. Our general result applies to some familiar kinds of structures, including some classes of linear orderings and trees. We do not get the result of Downey and Jockusch for arbitrary Boolean algebras, but we do get a result for Boolean algebras with no $1$-atom, with some extra information on the complexity of the isomorphism. Our general result gives the result of Marker and Miller. In order to apply our general result, we produce a computable enumeration of the types realized in models of $DCF_0$. This also yields the fact that the saturated model of $DCF_0$ has a decidable copy.

The generalized constraint language (GCL), introduced by Zadeh, serves as a basis for computing with words (CW). It provides an agenda to express the imprecise and fuzzy information embedded in natural language and allows reasoning with perceptions. Despite its fundamental role, the definition of GCL has remained informal since its introduction by Zadeh, and to our knowledge, no attempt has been made to formulate a rigorous theoretical framework for GCL. Such formalization is necessary for further theoretical and practical advancement of CW for two important reasons. First, it provides the underlying infrastructure for the development of useful inference patterns based on sound theories. Second, it determines the scope of GCL and hence facilitates the translation of natural language expressions into GCL. This paper is an attempt to step in this direction by providing a formal syntax together with a compositional semantics for GCL. A soundness theorem is defined, and Zadeh's deduction rules are proved to be valid in the defined semantics. Furthermore, a discussion is provided on how the proposed language may be used in practice.

We examine the relation of BSS-reducibility on subsets of the real numbers. The question was asked recently (and anonymously) whether it is possible for the halting problem H in BSS-computation to be BSS-reducible to a countable set. Intuitively, it seems that a countable set ought not to contain enough information to decide membership in a reasonably complex (uncountable) set such as H. We confirm this intuition, and prove a more general theorem linking the cardinality of the oracle set to the cardinality, in a local sense, of the set which it computes. We also mention other recent results on BSS-computation and algebraic real numbers.

Abstract This paper calculates, in a precise way. the complexity of the index sets for three classes of computable structures: the class of structures of Scott rank , the class , of structures of Scott rank , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete is m-complete relative to Kleene's and is m-complete relative to .

Abstract Makkai [10] produced an arithmetical structure of Scott rank ω1CK. In [9], Makkai's example is made computable. Here we show that there are computable trees of Scott rank ω1CK. We introduce a notion of “rank homogeneity”. In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated “group trees” of [10] and [9], Using the same kind of trees, we obtain one of rank ω1CK that is “strongly computably approximable”. We also develop some technology that may yield further results of this kind.

Abstract Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.