Iskander .Sh. Kalimullin, On the Group Generated by Primitive Recursive Permutations

Let C be the group of all computable permutations of w. Let P $\subset$ C be the class of all primitive recursive permutations. Consider the subgroup <P>. It is the least subgroup containing P. We prove that <P> = C. To obtain this result we consider the class P₁ $\subseteq$ <P> of computable permutations which are presentable as pt^-1, where p and t are primitive recursive permutations. We also study the class P₂ $\subseteq$ <P> of functions which are presentable as a superposition of two permutations from P₁.

It is shown that each computable permutation can be presented as a superposition of a permutation from P₁ and a permutation from P₂.

Oleg V. Kudinov, Complexity of Problems in Computable Model Mheory and Categoricity

For any countable model A it is natural to consider the set of Turing degrees dg(A) = { a | for some model B @ A with domain |B| $\subseteq$ w the atomic diagram of (A,a)_{a $\in$ |A|} has a degree a }.

It is well-known that this set does not necessary possess the least degree. This fact leads us to the following natural Goncharov's problem. Do there exist Turing degrees a|b that for a suitable countable model A dg(A) = { d | d $\geq$ a or d $\geq$ b}?

This problem is still open but for c.e. degrees the answer is negative.

Theorem 1 For any countable model A its dg(A) cannot be presented in the form
{ d | d $\geq$ a or d $\geq$ b} for some incomparable c.e. degrees a,b.

To take into account a difference between nonequivalent presentations of given model A, one can define a function Sp_A (A):D -> wu{ w} by the rule: Sp_A (A) (d) is equal to quantity of presentations of A of degree d up to equivalence being defined via computable in d isomorphisms between presentations. In particular, d $\in$ dg(A) iff Sp_A (A)(d) > 0.

Remark 1 A computable model A is relatively categorical iff it possesses a computable Scott family of existential formulas (with finite number of parameters) iff "d  Sp_A (A)(d) = 1.

There are some known restrictions on functions Sp_A - the problem is to describe them.

As for the problem of existence of a computable copy for given model, it is reduced to similar problem for the computable fragment of L_{w1, w}.

Theorem 2 A model M has a computable copy iff for every constructive ordinal a the set of realized in M computable infinitary sentences of rank bounded by a has a computable model.

To investigate important classes of models, let us fix any natural computable enumeration y of partial atomic diagrams of computable models in the language without functional symbols. Index set of the class of computable models defined via y measures its complexity.

Theorem 3 The index set of the class of categorical models is m-complete in P¹₁.
The index set of the class of categorical 1-decidable models is m-complete in P⁰₄.

Steffen Lempp, On Computable Self-Embeddings of Computable Linear Orders

The Dushnik-Miller Theorem for countable linear orders states that any countably infinite linear order L has a nontrivial self-embedding (i.e., an order-preserving injection f from L into L). By a result of Hay and Rosenstein, this theorem does not hold effectively.

An old problem, that has been open for several decades, asks for a characterization of those countably infinite order types t such that all computable presentations of t allow a nontrivial computable self-embedding.

It has been conjectured by Lerman, Watnick and others that these order types are exactly those t such that any infinite interval I of t admits a fixed finite bound n_I on the size of discrete subintervals of I. Downey has shown that if this conjecture holds, then it cannot hold uniformly, and it is not sufficient to consider only D⁰₂-isomorphisms.

Along these lines, I will present two related, joint results:

1. Jointly with Downey, I showed that there is an infinite computable linear order L such that any nontrivial self-embedding of L computes the halting problem. As a corollary, we obtain that the Dushnik-Miller Theorem for countable linear orders is equivalent to ACA₀ over RCA₀.

2. Jointly with McCoy, Morozov and Solomon, I constructed an infinite computable linear order L without D⁰₂-computable nontrivial self-embedding.

The conjecture above remains open and still appears very hard.

Angsheng Li, Splitting and Nonsplitting in the Computably Enumerable Degrees

The study of splitting and nonsplitting has been a basic topic since the beginning of the study of the Turing degrees, the results in this area added to a growing impression of structural pathology, and the proof of results in this area provided one of the main technical resourses in the computability theory. First we survey the basic results about the splitting and nonsplitting of the c.e. degrees; secondly we introduce some results about the relationship of splitting and nonsplitting and the high/low hierarchy, which are viewed as aids to establishing Turing definability, in particular, we introduce a new nonsplitting theorem of Cooper and Li [ta2]: there exists a low₂ c.e. degree above which 0¢ is not splittable; finally, we introduce the solution to Lachlan's major subdegree problem, Cooper and Li [ta3] have shown that every c.e. degree b not equal to 0,0¢ has a major subdegree. A consequence of this theorem is the continuity of the Harrington nonsplitting base that there is no minimal Harrington nonsplitting base, where a Harrington nonsplitting base is an incomplete c.e. degree above which 0¢ is not splittable.

We claim to suggest a natural definition of Turing degrees over admissible ordinals. We discuss the notion of S-definability of admissible sets introduced and studied in [1]. In our view, Turing degrees correspond to computational devices given by admissible sets while the S-definability of one admissible set in another corresponds to algorithmic reducibility.

In the criterion of S-definability for locally countable recursively listed admissible sets we proved in [1], S-definable permutations were involved. New criterion is easier and is applicable to a wider class of admissible sets.

Theorem. Assume \mathbb A and \mathbb B are recursively listed admissible sets. Then \mathbb A is S-definable over \mathbb B if and only if each D-subset of o(\mathbb A) is a D-subset of o(\mathbb B).

Related problems are discussed.

References

1. A.S.Morozov, On S-definability of admissible sets, In: Proceedings of logic Colloquium-98, Praha, 9-15 August, S. Buss, P. Hájek, P. Pudlák eds. p. 334-351.

We use methods from effective algebra to prove the undecidability of the theory of various distributive structures. The structures stem from computability theory, complexity theory and formal logic. We also discuss new results on the Solovay degrees of c.e. reals

Sets of integers and integer-valued functions as well as integers themselves are main objects of classical algorithm theory. When we have described an enumeration procedure for a set of integers depending of few external parameters, by s-m-n-theorem (Parameter Theorem), we can effectively in the parameters find a recursively enumerable index of the set of integers resulting. This is some general method to obtain various results in algorithm theory based on the using of the Parameter Theorem.

Constructions of finitely axiomatizable theories can be considered as some kind of Parameter Theorem. When we have described an effective enumeration procedure (depending of some external parameters) for a set of first-order formulas which determines a theory, applying a construction of finitely axiomatizable theory, we can effectively in the parameters find a single first-order formula that (in known sense) has the same model-theoretic properties as the recursively axiomatizable theory we initially constructed. This gives very general and powerful method to obtain particular results about algorithmic properties of formulas in first-order predicate logic.

This idea gives a very natural extension of classical algorithm theory on new (very interesting) objects - first order formulas (which are considered together with their model-theoretic contents).

Hausdorff dimension is an important tool in geometric measure theory, especially in the study of fractal objects. It refines Lebesgue measure, thereby allowing to distinguish quantitatively between Lebesgue nullsets. For instance, the well known middle third Cantor set is a set of measure zero having Hausdorff dimension log2 / log3.

In the context of computability, originating from applications of Hausdorff dimension in information theory, a close connection between Hausdorff dimension and Kolmogorov complexity was established. This led to the definition of effective dimension.

Recently, Lutz has extended the theory of effective dimension to complexity theory by introduc ing resource-bounded dimension. As in the case of resource bounded measure, the resource bound is imposed on the martingales (betting strategies) characterizing the Hausdorff dimension of a class.

This talk focuses on the resource-bounded dimension of objects in structural complexity theory. The main results (among others) are:

1. For every set in E, the dimension of its p-m-degree is the same as the dimension of its p-m-lower span. (This implies that the p-m-complete sets have dimension 1 in E, thereby yielding an example of a class that has measure 0 but dimension 1 in E.)

2. For every D⁰₂-computable real a from [0,1] there is a set whose p-m-lower span has dimension a in E.

We recall that a set A (subset of the set w of the natural numbers) is enumeration reducible to B (A £ _eB) if there is a uniform algorithm for obtaining the enumeration of the members of A from any given enumeration of B. We denote by d_e(A) the e-degree of A, and by D_e the upper semilattice of the e-degrees. Let Tot be the subset of D_e consisted of the total e-degrees. We are interested in two problems about D_e\Tot:

(i) what can we say about the e-degrees from D_e\Tot moreover they are non-total;

(ii) to characterizate the non-total e-degrees in terms of properties of some of their elements.

The examination of the first problem resulted in the following

Theorem. Let b by any given e-degree then any non-total e-degree a=d_e(A) such that b £ a < b¢ either is a c-quasi-minimal for certain e-degree c $\geq$ b or a contains the set E = $\bigcup_{s \in \omega$} E_s, where E₀ < _eE₁ < _e... < _eE_s < _e... < _eA and d_e(E_s) in Tot for all s ‘ w. Incidentally, if b in Tot then d_e(E₀)=b.

The second problem does not have a best possible solution for the present. We give a series of the sufficient conditions for non-totality of the e-degrees in terms of the specially chosen classes of sets, of a strong e-reducibility and of T-reducibility.

The main question addressed in the present work is how to find effectively a recursive function separating two sets drawn arbitrarily from a given collection of disjoint sets. In particular, it is investigated in which cases it is possible to satisfy the following additional constraints: confidence where the learner converges on all data-sequences; conservativeness where the learner abandons only definitely wrong hypotheses; consistency where also every intermediate hypothesis is consistent with the data seen so far; set-driven learners whose hypotheses are independent of the order and the number of repetitions of the data-items supplied; learners where either the last or even all hypotheses are programs of total recursive functions.

The present work gives an overview of the relations between these notions and succeeds to answer many questions by finding ways to carry over the corresponding results from other scenarios within inductive inference. Nevertheless, the relations between conservativeness and set-driven inference needed a novel approach which enabled to show the following two major results:

1. There is a class for which recursive separators can be found in a confident and set-driven way, but no conservative learner finds a (not necessarily total) separator for this class.
2. There is a class for which recursive separators can be found in a confident and conservative way, but no set-driven learner finds a (not necessarily total) separator for this class.