Minimal generalized computable enumerations and high degrees

We establish that the set of minimal generalized computable enumerations of every infinite family computable with respect to a high oracle is effectively infinite. We find some sufficient condition for enumerations of the infinite families computable with respect to high oracles under which there exist minimal generalized computable enumerations that are irreducible to the enumerations.     

Relativized Schnorr tests with universal behavior

A Schnorr test relative to some oracle A may informally be called “universal” if it covers all Schnorr tests. Since no true universal Schnorr test exists, such an A cannot be computable. We prove that the sets with this property are exactly those with high Turing degree. Our method is closely related to the proof of Terwijn and Zambella’s characterization of the oracles which are low for Schnorr tests. We also consider the oracles which compute relativized Schnorr tests with the weaker property of covering all computable reals. The degrees of these oracles strictly include the hyperimmune degrees and are strictly included in the degrees not computably traceable.     

Some effectively infinite classes of enumerations

This research partially answers the question raised by Goncharov about the size of the class of positive elements of a Roger's semilattice. We introduce a notion of effective infinity of classes of computable enumerations. Then, using finite injury priority method, we prove five theorems which give sufficient conditions to be effectively infinite for classes of all enumerations without repetitions, positive undecidable enumerations, negative undecidable enumerations and all computable enumerations of a family of r.e. sets. These theorems permit to strengthen the results of Pour-El, Pour-El and Howard, Ershov and Khutoretskii about existence of enumerations without repetitions and positive undecidable enumerations.     

Lattice embeddings and array noncomputable degrees

We focus on a particular class of computably enumerable (c. e.) degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to lattice embeddings and definability in the partial ordering (??, ≤) of c. e. degrees under Turing reducibility. We demonstrate that the latticeM₅ cannot be embedded into the c. e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M₅ can be embedded below every nonlow₂ degree, our result is the best possible in terms of array noncomputable degrees and jump classes. Further, this result shows that the array noncomputable degrees are definably different from the nonlow₂ degrees. We note also that there are embeddings of M₅ in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0 but the other four are array noncomputable. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Universal computable enumerations of finite classes of families of total functions

In the paper we introduce the notion of a computable enumeration of a class of families. We prove a criteria for the existence of universal computable enumerations of finite classes of computable families of total functions. In particular, we show that there is a finite computable class of families of total functions without universal computable enumerations.     

Modulo computably enumerable degrees by cupping partners

Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree.     

Rogers Semilattices for Families of Equivalence Relations in the Ershov Hierarchy

Siberian Mathematical Journal - The paper studies Rogers semilattices for families of equivalence relations in the Ershov hierarchy. For an arbitrary notation a of a nonzero computable ordinal, we...     

The class of projective planes is noncomputable

Computable projective planes are investigated. It is stated that a free projective plane of countable rank in some inessential expansion is unbounded. This implies that such a plane has infinite computable dimension. The class of all computable projective planes is proved to be noncomputable (up to computable isomorphism).     

Initial Segments in Rogers Semilattices of \Sigma _n^0 -Computable Numberings

S. Goncharov and S. Badaev showed that for , there exist infinite families whose Rogers semilattices contain ideals without minimal elements. In this connection, the question was posed as to whether there are examples of families that lack this property. We answer this question in the negative. It is proved that independently of a family chosen, the class of semilattices that are principal ideals of the Rogers semilattice of that family is rather wide: it includes both a factor lattice of the lattice of recursively enumerable sets modulo finite sets and a family of initial segments in the semilattice of -degrees generated by immune sets.     

Noncomputability,unpredictability, and financial markets

One of the most significant achievements from theoretical computer science was to show that there are noncomputable problems, which cannot be solved through algorithms. Although the formulation of such problems is mathematical, they often can be interpreted as problems derived from other fields, like physics or computer science. However, no non‐computable problem with economical or financial inspiration has been presented before. Here, we study the problem of valuation: given some adequate data, find the value of an asset. Valuation is modeled mathematically by the discounted cash flow operator. We show, using surprisingly simple arguments, that this operator is not computable. As theoretically, financial markets should trade assets based on their fair value, our result suggests that unpredictability of such markets may partially stem from inherent noncomputable behavior. A discussion of this result is also included. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Isomorphism of the Index Sets of Discrete Families of General Recursive Functions

We establish isomorphism between the index set of an arbitrary computable family of general recursive functions and the index set of a certain computable discrete family of general recursive functions.     

Negative Dense Linear Orders

Considering dense linear orders, we establish their negative representability over every infinite negative equivalence, as well as uniformly computable separability by computable gaps and the productivity of the set of computable sections of their negative representations. We construct an infinite decreasing chain of negative representability degrees of linear orders and prove the computability of locally computable enumerations of the field of rational numbers.     

Degree spectra and immunity properties

We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Rogers Semilattices of Finite Partially Ordered Sets

It is proved that the principal sublattice of a Rogers semilattice of a finite partially ordered set is definable. For this goal to be met, we present a generalization of the Denisov theorem concerning extensions of embeddings of Lachlan semilattices to ideals of Rogers semilattices.     

Limitwise monotonic sets of reals

We extend the limitwise monotonicity notion to the case of arbitrary computable linear ordering to get a set which is limitwise monotonic precisely in the non‐computable degrees. Also we get a series of connected non‐uniformity results to obtain new examples of non‐uniformly equivalent families of computable sets with the same enumeration degree spectrum.     

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.     

Constructive equivalence relations on computable probability measures

A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences.In what follows, we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general.     

A Note on Hilbert Algebras and Their Related Generalized Esakia Spaces

Generalized Esakia spaces are the topological duals of bounded implicative semilattices in the duality studied by G. Bezhanishvili and R. Jansana. We study the relation between a Hilbert algebra and the generalized Esakia space dual to its free implicative semilattice extension. To establish the relation we introduce a category whose objects are a generalized Esakia space together with a family of clopen up-sets that constitutes a subalgebra of the implication fragment of the Heyting algebra of the up-sets of the generalized Esakia space.