Reduction of computable and potentially computable numerations

Among the numerations of classes of countable sets there can be distinguished those in which the number contains information about the set having the number-these are computable and potentially computable numerations—and those in which the set contains information about its number-these are covering and fully covering numerations. The conditions are established which are necessary and sufficient in order that all numerations of the given class should be covering. As a corollary it is established that there exist covering numerations which are not fully covering.Translated from Matematicheskie Zametki, Vol. 6, No. 1, pp. 3–9, July, 1969.     

Generalized computable numerations and nontrivial rogers semilattices

We outline the general approach to the notion of a computable numeration in the frames of which computable numerations, of families of arithmetic sets are studied. Supported by RECO grant NERBCHRXCT 930415 and by RFFR grant No. 096-01-01525 Supported by RECO grant NERBCIPDCT 940615 Translated fromAlgebra i Logika, Vol. 36, No. 6, pp. 621–641, November-December, 1997.     

Existence of families without positive numerations

An example is constructed of a computable family of recursively enumerable sets which does not have computable positive numerations but does possess a computable minimal numeration.Translated from Matematicheskie Zametki, Vol. 13, No. 4, pp. 597–604, April, 1973.     

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.     

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.     

Superautonomous numerations and projected ordinals

Translated from Algebra i Logika, Vol. 30, No. 1, pp. 28–47, January–February, 1991.     

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.     

Principal numerations of functionals on admissible sets

Translated from Algebra i Logika, Vol. 29, No. 4, pp. 398–420, July–August, 1990.     

When series of computable functions with varying domains are computable

In this paper we study the behavior of computable series of computable partial functions with varying domains (but each domain containing all computable points), and prove that the sum of the series exists and is computable exactly on the intersection of the domains when a certain computable Cauchyness criterion is met. In our point‐free approach, we name points via nested sequences of basic open sets, and thus our functions from a topological space into the reals are generated by functions from basic open sets to basic open sets. The construction of a function that produces the sum of a series requires working with an infinite array of pairs of basic open sets, and reconciling the varying domains. We introduce a general technique for using such an array to produce a set function that generates a well‐defined point function and apply the technique to a series to establish our main result. Finally, we use the main finding to construct a computable, and thus continuous, function whose domain is of Lebesgue measure zero and which is nonextendible to a continuous function whose domain properly includes the original domain. (We had established existence of such functions with domains of measure less than ε for any , in an earlier paper.)