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.     

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.     

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.     

Countably categorical and autostable Boolean algebras with distinguished ideals

We study countable Boolean algebras with finitely many distinguished ideals (countable I-algebras) whose elementary theory is countably categorical, and autostable I-algebras which form their subclass. We propose a new characterization for the former class that allows to answer a series of questions about the structure of countably categorical and autostable I-algebras.     

Uniformity in Computable Structure Theory

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.     

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.     

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.     

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 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.     

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.     

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.     

Estimation of the algorithmic complexity of classes of computable models

We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Σ ₂ ⁰ -complete), computable models with ω-categorical theories (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), prime models (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), models with ω ₁-categorical theories (Δ _ω ⁰ -complex Σ _ω+1 ⁰ -set. We obtain a universal lower bound for the model-theoretic properties preserved by Marker’s extensions (Δ _ω ⁰ .     

Monotonically Computable Real Numbers

Area number x is called k‐monotonically computable (k‐mc), for constant k > 0, if there is a computable sequence (x_n)_{n ∈ ℕ} of rational numbers which converges to x such that the convergence is k‐monotonic in the sense that k · |x — x_n| ≥ |x — x_m| for any m > n and x is monotonically computable (mc) if it is k‐mc for some k > 0. x is weakly computable if there is a computable sequence (x_s)_{s ∈ ℕ} of rational numbers converging to x such that the sum $\sum _{s \in \mathbb{N}}$|x_s — x_{s + 1}| is finite. In this paper we show that a mc real numbers are weakly computable but the converse fails. Furthermore, we show also an infinite hierarchy of mc real numbers.     

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.     

A generalized Feiner hierarchy

We study some properties of a generalization of the Feiner hierarchy of Δ _ω ⁰ -computable functions and consider various conditions for the inclusion of one class of this hierarchy into another.     

Necessary Isomorphism Conditions for Rogers Semilattices of Finite Partially Ordered Sets

We establish a condition that is necessary for Rogers semilattices of computable numberings of finite families of computably enumerable sets to be isomorphic.     

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.     

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)     

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.