Computable Structure and Non-Structure Theorems

In a lecture in Kazan (1977), Goncharov dubbed a number of problems regarding the classification of computable members of various classes of structures. Some of the problems seemed likely to have nice answers, while others did not. At the end of the lecture, Shore asked what would be a convincing negative result. The goal of the present article is to consider some possible answers to Shore's question. We consider structures of some computable language, whose universes are computable sets of constants. In measuring complexity, we identify with its atomic diagram D(), which, via the Gödel numbering, may be treated as a subset of . In particular, is computable if D() is computable. If K is some class, then K^c denotes the set of computable members of K. A computable characterization for K should separate the computable members of K from other structures, that is, those that either are not in K or are not computable. A computable classification (structure theorem) should describe each member of K^c up to isomorphism, or other equivalence, in terms of relatively simple invariants. A computable non-structure theorem would assert that there is no computable structure theorem. We use three approaches. They all give the correct answer for vector spaces over Q, and for linear orderings. Under all of the approaches, both classes have a computable characterization, and there is a computable classification for vector spaces, but not for linear orderings. Finally, we formulate some open problems.     

Computable Families of Superatomic Boolean Algebras

We describe the families of superatomic Boolean algebras which have a computable numbering. We define the notion of majorizability and establish a criterion that is formulated only on using algorithmic terms and majorizability. We give some examples showing that the condition of majorizability is essential. We also prove some criterion for the existence of a computable numbering for a family of -atomic algebras ( is a computable ordinal).     

On computable formal concepts in computable formal contexts

We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.     

Constructive and Non-Constructive Infinite Formulas in Computable Structures

A transition from arbitrary -formulas to computable formulas in the class of computable structures is considered. It is shown that transition of a certain type is possible which doubles the complexity of the formulas. In addition, the complexity jump is analyzed for the transition from an arbitrary Scott family consisting of -formulas to a computable Scott family in a fixed computable structure. Exact estimates of this jump are found.     

Degree Spectra of Relations on Boolean Algebras

We show that every computable relation on a computable Boolean algebra is either definable by a quantifier-free formula with constants from (in which case it is obviously intrinsically computable) or has infinite degree spectrum.     

Complexity of Categorical Theories with Computable Models

M. Lerman and J. Scmerl specified some sufficient conditions for computable models of countably categorical arithmetical theories to exist. More precisely, it was shown that if T is a countably categorical arithmetical theory, and the set of its sentences beginning with an existential quantifier and having at most n+1 alternations of quantifiers is _n+1 ⁰ for any n, then T has a computable model. J. Night improved this result by allowing certain uniformity and omitting the requirement that T is arithmetical. However, all of the known examples of theories of₀-categorical computable models had low level of algorithmic complexity, and whether there are theories that would satisfy the above conditions for sufficiently large n was unknown. This paper will include such examples.     

Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.     

Index sets and Scott sentences

For a computable structure \({\mathcal{A}}\) , there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence \({\varphi}\) , then the complexity of the index set \({I(\mathcal{A})}\) is bounded by that of \({\varphi}\) . There are results (Ash and Knight in Computable structures and the hyperarithmetical hierarchy. Elsevier, Amsterdam, 2000; Calvert et al. in Algeb Log 45:306–315, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012; Knight and Saraph in Scott sentences for certain groups, pre-print) giving “optimal” Scott sentences for structures of various familiar kinds. These results have been driven by the thesis that the complexity of the index set should match that of an optimal Scott sentence (Ash and Knight in Computable structures and the hyperarithmetical hierarchy. Elsevier, Amsterdam, 2000; Calvert et al. in Algeb Log 45:306–315, 2006; Carson et al. in Trans Am Math Soc 364:5715–5728, 2012; McCoy and Wallbaum in Trans Am Math Soc 364:5729–5734, 2012). In this note, it is shown that the thesis does not always hold. For a certain subgroup of \({\mathbb{Q}}\) , there is no computable d- \({\Sigma_2}\) Scott sentence, even though (as shown in Ash and Knight in Scott sentences for certain groups, pre-print) the index set is d- \({\Sigma^0_2}\) .     

Hyperarithmetical Boolean Algebras with a Distinguished Ideal

We prove a general theorem that allows us to pass from a hyperarithmetical Boolean algebra with a distinguished ideal to some computable Boolean algebra connected with the former by natural algebraic operations. Some examples are given.     

The Degree Spectra of Definable Relations on Boolean Algebras

We study some questions concerning the structure of the spectra of the sets of atoms and atomless elements in a computable Boolean algebra. We prove that if the spectrum of the set of atoms contains a 1-low degree then it contains a computable degree. We show also that in a computable Boolean algebra of characteristic (1, 1, 0) whose set of atoms is computable the spectrum of the atomless ideal consists of all Π ₀ ² degrees.Original Russian Text Copyright © 2005 Semukhin P. M.The author was supported by the Russian Foundation for Basic Research (Grant 02-01-00593), the Leading Scientific Schools of the Russian Federation (Grant NSh-2112.2003.1), and the Program “Universities of Russia” (Grant UR.04.01.013).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 928–941, July–August, 2005.     

The Computable Dimension of I-Trees of Infinite Height

We study computable trees with distinguished initial subtree (briefly, I-trees). It is proved that all I-trees of infinite height are computably categorical, and moreover, they all have effectively infinite computable dimension.     

A uniformly computable Implicit Function Theorem

We prove uniformly computable versions of the Implicit Function Theorem in its differentiable and non‐differentiable forms. We show that the resulting operators are not computable if information about some of the partial derivatives of the implicitly defining function is omitted. Finally, as a corollary, we obtain a uniformly computable Inverse Function Theorem, first proven by M. Ziegler (2006). (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Noncomputability,unpredictability, undecidability,and unsolvability in economic and finance theories

We outline, briefly, the role that issues of the nexus between noncomputability and unpredictability, on the one hand, and between undecidability and unsolvability, on the other hand, have played in Computable Economics (CE). The mathematical underpinnings of CE are provided by (classical) recursion theory, varieties of computable and constructive analysis and aspects of combinatorial optimization. The inspiration for this outline was provided by Professor Graça's thought‐provoking recent article. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Boolean Algebras with Finite Families of Computable Automorphisms

We prove that each computable Boolean algebra has a computable presentation in which for every computable family of automorphisms the set of atoms moved by at least one of its members is finite. This implies that each computable atomic Boolean algebra has a computable presentation in which its every computable family of automorphisms is finite. The priority argument is not used in the proof.     

Is wave propagation computable or can wave computers beat the turing machine?

According to the Church-Turing Thesis a number function is computableby the mathematically defined Turing machine if and only ifit is computable by a physical machine. In 1983 Pour-El andRichards defined a three-dimensional wave u(t,x) such that theamplitude u(0,x) at time 0 is computable and the amplitude u(1,x)at time 1 is continuous but not computable. Therefore, theremight be some kind of wave computer beating the Turing machine.By applying the framework of Type 2 Theory of Effectivity (TTE),in this paper we analyze computability of wave propagation.In particular, we prove that the wave propagator is computableon continuously differentiable waves, where one derivative islost, and on waves from Sobolev spaces. Finally, we explainwhy the Pour-El-Richards result probably does not help to designa wave computer which beats the Turing machine. 2000 Mathematical Subject Classification: 03D80, 03F60, 35L05,68Q05.     

Stability of representations of effective partial algebras

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings (theorems of Moschovakis and Hertling). To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On Classifying Subsets of Natural Numbers by Their Computable Permutations

We introduce some alternative definitions of the concept of computable automorphism of a set of natural numbers. We study their relationships and investigate whether some classes of sets having isomorphic groups of automorphisms coincide with other classes of sets usual in computability. Finally, we show that the classification of sets by these groups of automorphisms is nontrivial.     

Spectra of computable models for Ehrenfeucht theories

We construct an example of a theory with a finite (greater than one) number of isomorphism types of countable models such that its prime and saturated models have computable presentations and there exists a model which lacks in such. Supported by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-4413.2006.1. __________ Translated from Algebra i Logika, Vol. 46, No. 3, pp. 275–289, May–June, 2007.