Search

This paper is a companion to work of Feferman, Jäger, Glaß, and Strahm on the proof theory of the type two functionals μ and E1 in the context of Feferman-style applicative theories. In contrast to the previous work, we analyze these two functionals in the context of Schlüter's weakened applicative basis PRON which allows for an interpretation in the primitive recursive indices. The proof-theoretic strength of PRON augmented by μ and E1 is measured in terms of the two subsystems of second order arithmetic, Π10-CA and Π11-CA, respectively. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains (i. e. complements of domains) of recursive quantum functions and hence with avoidable points (i. e. points that can be forced into exdomains of recursive quantum functions). An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an arbitrary subset of the avoidable points of a single avoidance function, and we study an effective union of such sets which we call a piecemeal avoidable set. We note that each of ‘the set of recursive points’ and ‘the set of avoidable points’ is of first category but not recursively of first category. We show an exdomain exists which is recursively nowhere dense, as well as one that is nowhere dense but not recursively nowhere dense. After establishing that every exdomain is recursively of first category, we prove that given any fixed exdomain, there is another exdomain, which while dense in the underlying space, is disjoint from the fixed exdomain. Finally, we show how to build a recursive sequence of recursive quantum functions that have mutually disjoint, dense exdomains. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We investigate connections between the syntactic and semantic distance of programs on an abstract, recursion theoretic level. For a certain rather restrictive notion of interdependency of the two kinds of distances, there remain only few and “unnatural” numberings allowing such close relationship. Weakening the requirements leads to the discovery of universal metrics such that for an arbitrary recursively enumerable family of functions a numbering compatible with such a metric can uniformly be constructed. We conclude our considerations with some implications on learning theory. [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.

The article presents a research study which defines the notion called k-immunity which can be found between immunity and hyperimmunity in strength. It examines the findings that ϕ' does not k-tt reduce to a k-immune set which justified the concepts of k-immunity. It also applies the result to MIN, the set of minimal programs, to show that ϕ' cannot btt-reduce to MIN.

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 considers a fault tolerant version for effective search problems and relates it with Ulam's game. The authors obtain tight upper and lower bounds on the query complexity of F for many natural classes of functions F. They seek a minimal number that can be achieved by a suitable choice of X.

The article describes a theorem for certain classes of recursive infinitary formulas. It considers the following generalization of the notion of a structure recursive relative to a set X. It demonstrates that a certain, fairly obvious, description of classes C', of recursive infinitary formulas has a property.

The article examines the cohesive degrees of unsolvability of sets. It has proven that every strongly hyperimmune set whose degree contains either a Boolean combination or a generic set is of high degree. Moreover, the corresponding degrees are also characterized in relation to the primitive recursive analogues of the notion.

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 discusses how to use homogeneous trees to obtain complicated descending sequences of ordinals instead of ordinal notations. It states that Jussi Ketonen's developed a theory of large finite sets wherein the descending sequences of ordinals can be coded as sequences of natural numbers. It details two ways of obtaining descending sequences in well-founded trees and ordinal notations as well as how to define recursion on the tree-ordering of homogeneous trees.

The article discusses the recursion and existence theoretic properties of real generic sets. It mentions that most structures of recursion theory apply the method of forcing. It notes the Friedberg Jump theorem which can be established through further construction of a 1-generic set. It points out the low turning degrees of the sets as well as the notion of genericity that has an analogue in the theory over the domain of objects.

The article discusses the basic recursive notions for fuzzy sets. It tackles on the general theory of recursive equivalence types of fuzzy sets and fuzzily recursively infinite sets. It defines the union, intersection and complement using S and T as fuzzy sets with characteristic functions. It tackles on the stronger version of reducibility and equivalence as well as fuzzy isolation.

The article presents a study which focuses on the development of an arithmetical measure theory based on the approach of J.H. Lutz. The arithmetic measure yielded same notion of measure 0 set as considered before the Martin-Löf randomness. The location of the class of r.e. sets through common recursion-theoritic reducibilities is highlighted,

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 discusses the properties needed in proving various results from recursion theory. It states that the usual setting for recursion theory is the standard model for second order arithmetic. It identifies relatively recursively enumerable versus a certain relatively formula in models of Peano Arithmetic (PA). It defines the set of forcing conditions.

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.