Search

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales. At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover. [ABSTRACT FROM AUTHOR]

We introduce the concept of a generic relation for algorithmic problems, which preserves the property of being decidable for a problem for almost all inputs and possesses the transitive property. As distinct from the classical m-reducibility relation, the generic relation under consideration does not possess the reflexive property: we construct an example of a recursively enumerable set that is generically incomparable with itself. We also give an example of a set that is complete with respect to the generic relation in the class of recursively enumerable sets. [ABSTRACT FROM AUTHOR]

Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as $\mathcal{O}^{(\omega)}$ or, equivalently, that of the truth set of $L_{\omega_{1}^{CK}}$.. [ABSTRACT FROM AUTHOR]

In this paper we prove that any c. e. degree is splittable with an c. e. infimum over any lesser c. e. degree in the class of d-c. e. degrees. [ABSTRACT FROM AUTHOR]

The article focuses on a class of recursively enumerable (r.e.) sets, considering r.e. sets as an amount of information content. It demonstrates that an integer n can be considered both an index of a r.e. set of codes of information and a set of indices of such sets of information. It studies the properties of a class of sets by defining it as a natural closure of recursively enumerable sets.

We prove that there are two incomplete d.r.e.\ degrees (the Turing degrees of differences of two recursively enumerable sets) such that every non-zero recursively enumerable degree cups at least one of them to ${\bf 0}2$, the greatest recursively enumerable (Turing) degree. [ABSTRACT FROM AUTHOR]

The article presents a study investigating minimal degree for recursively inseparable sets. It is found that "effectively inseparable" could not be replaced by "recursively inseparable" as the set which separates a disjoint pair of recursively inseparable sets was unable to bound a minimal degree. It is also mentioned that, every degree of Peano Arithmetic (PA) model bounds a minimal degree.

The article discusses the Recursion Theory and characterizes families of finite sets of natural numbers which have an universal recursively enumerable (r.e.) set. Conditions for a union of the set of all recursive functions and a special family of finite initial functions to have an universal partial recursive (p.r.) function is presented. Conditions necessary for nonempty family of finite sets of natural numbers to be universal recursively enumerable set are also presented.

The article introduces the concept of decidable fuzzy subset. It generalizes mathematician Leon Harkleroad's definition of recursively enumerable fuzzy subsets. It describes some characterizations of recursively enumerable fuzzy subsets and explains when axiomatizable fuzzy theory can be considered as recursively enumerable and decidable. It also looks into the relationship between fuzziness and decidability.

The article presents a solution to a problem on Grzegorczyk hierarchy or classes. It introduces intermediate classes using bounded recursion schema. It presents basic notions and facts of the definition of Grzegorczyk classes. It also illustrates the replacement of bounded recursion by the short recursion (SR&#x006En;) schema.

The article presents a research related to recursion theory. It mentions certain recursively enumerable (R.E.) sets that possess low n and high n, which are redefined for R.E. degrees. It also mentions a certain set that features a bounded-truth-table degree that do not contain jump of R.E. sets, which generalizes results proven by C. Jockusch and G. Phillips.

The article presents a study on the noneffectively and effectively nowhere simple sets from recursively enumerable (r.e.) set. It argues that a r.e. set is a disjoint union of either two effectively nowhere sets or of two noneffectively nowhere simple sets. The author generalizes the results of J. Remmel and D. Miller studies on nowhere simple sets.

The article explores some lattice constructions in high recursively enumerable (R. E.) degrees. The constructions are carried any given high R. E. degree without maximal supersets. Every degree has a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. Refinements of known constructions are made.