On a Class of Recursively Enumerable Sets

We define a class of so-called ∑(n)-sets as a natural closure of recursively enumerable sets W_n under the relation “∈” and study its properties.     

Effectively and Noneffectively Nowhere Simple Sets

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ? of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non-nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ?*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ?*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ?*. Mathematics Subject Classification: 03D25, 03D10.     

Highness and bounding minimal pairs

We show the existence of a high r. e. degree bounding only joins of minimal pairs and of a high₂ nonbounding r. e. degree. MSC: 03D25.     

A New Reducibility between Turing- and wtt-Reducibility

A new reducibility between Turing and weak truth-table reducibility is defined, which gives an affirmative answer to the open question about the existence of such an intermediate reducibility proposed formally by M. Stob. Mathematics Subject Classification: 03D25.     

Graphs realised by r.e. equivalence relations

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders.     

Computable Real-Valued Functions on Recursive Open and Closed Subsets of Euclidean Space

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.     

Differences of Computably Enumerable Sets

We consider the ower semilattice 𝒟 of differences of c.e. sets under inclusion. It is shown that 𝒟 is not distributive as a semilattice, and that the c.e. sets form a definable subclass.     

A Note on Certain 2-Groups with Hadamard Difference Sets

Nontrivial difference sets in 2-groups are part of the family of Hadamarddifference sets. An abelian group of order 2^2d+2 has a difference setif and only if the exponent of the group is less than or equal to2 ^d+2. We provide an exponent bound for a more general type of 2-groupwhich has a Hadamard difference set. A recent construction due to Davis and Iiamsshows that we can attain this bound in at least half of the cases.     

Constructions of Partial Difference Sets and Relative DifferenceSets Using Galois Rings

We use Galois rings to construct partial difference sets and relative difference sets in non-elementary abelianp-groups. As an example, we also use Galois ringG R(4, 2) to construct a (96,20,4) difference set in Z₄ × Z₄ × Z₆.Dedicated to Hanfried Lenz on the occasion of his 80th birthday     

Effective Nonrecursiveness

Productive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifreddi [1].     

A Splitting with Infimum in the d‐c. e. Degrees

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.     

Friedberg Numberings of Families of n-Computably Enumerable Sets

We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all n-c.e. sets for any n>2. Second, it is stated that there exists an infinite family of d.c.e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c.e. sets (treated as a family of d.c.e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d.c.e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility).     

Sets characterized by missing sums and differences

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We show that the probability that a uniform random subset of {0,1,…,n} is an MSTD set approaches some limit ρ>4.28×¹⁰−4. This improves the previous result of Martin and O?Bryant that there is a lower limit of at least 2×¹⁰−7. Monte Carlo experiments suggest that ρ≈4.5×¹⁰−4. We present a deterministic algorithm that can compute ρ up to arbitrary precision. We also describe the structure of a random MSTD set S⊆{0,1,…,n}. We formalize the intuition that fringe elements are most significant, while middle elements are nearly unrestricted. For instance, the probability that any “middle” element is in S approaches 1/2 as n→∞, confirming a conjecture of Miller, Orosz, and Scheinerman. In general, our results work for any specification on the number of missing sums and the number of missing differences of S, with MSTD sets being a special case.     

Infimum Properties Differ in the Weak Truth-table Degrees and the Turing Degrees

Abstract We prove that there are non-recursive r.e. sets A and C with A < _T C such that for every set . Both authors are supported by “863” and the National Science Foundation of China     

Difference Sets and Hyperovals

We construct three infinite families of cyclic difference sets, using monomial hyperovals in a desarguesian projective plane of even order. These difference sets give rise to cyclic Hadamard designs, which have the same parameters as the designs of points and hyperplanes of a projective geometry over the field with two elements. Moreover, they are substructures of the Hadamard design that one can associate with a hyperoval in a projective plane of even order.     

The Isolated D. R. E. Degrees are Dense in the R. E. Degrees

In the present paper we prove that the isolated differences of r. e. degrees are dense in the r. e. degrees. Mathematics Subject Classification: 03D25.     

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.     

Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

Abelian Difference Sets Without Self-conjugacy

We obtain some results that are useful to the study of abelian difference sets and relative difference sets in cases where the self-conjugacy assumption does not hold. As applications we investigate McFarland difference sets, which have parameters of the form v=q^d+1( q^d+ q^d-1 +...+ q+2) ,k=q^d( q^d+q^d-1+...+q+1) , = q^d ( q^(d-1)+q^(d-2)+...+q+1), where q is a prime power andd a positive integer. Using our results, we characterize those abelian groups that admit a McFarland difference set of order k- = 81. We show that the Sylow 3-subgroup of the underlying abelian group must be elementary abelian. Our results fill two missing entries in Kopilovich's table with answer no.     

Splittings of 0' into the Recursively Enumerable Degrees

Lachlan [9] proved that there exists a non-recursive recursively enumerable (r. e.) degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a₀, a₁ such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b₀, b₂ such that w = b₀ V b₁ and b_i for i = 0, 1. Mathematics Subject Classification: 03D25, 03D30.