Abstract: A Т-complete wtt-mitotic set is composed, which is not tt-mitotic. A relation is found out between structure of computably enumerable sets and the density of their unsolvability degrees. Let us adduce some definitions: A computably enumerable (c.e.) set is tt - mitotic (wtt - mitotic) set if it is the disjoint union of two c.e. sets both of the same tt -degree ( wtt -degree) of unsolvability. Let A be an infinite set. f majorize A if ( ( ) ) n ∀n f n ≥ z , where z0 ,z1, are the members of A in strictly increasing order. A is hyperimmune (abbreviated h-immune) if A is infinite and (∀ recursive f ) f does not majorize A. A is hypersimple if A is c.e. and A is hyperimmune. A is hyperhyperimmune if A is infinite and ¬(∃ recursive f ) so that [( ) &( )( ) ∀u Wf (u) is finite & Wf (u)  A ≠ ∅ ∀u ∀v u ≠ v ⇒Wf (u) Wf (v) = ∅ ]. A is hyperhypersimple if A is computably enumerable and A is hyperhyperimmune. We shall denote T-degrees by small bold Latin letters. A degree a ≤ 0′ is low if a′ = 0′(i.e. if the jumpa′ has the lowest degree possible). Theorem (Martin 6). a is the degree of a maximal set ⇔ a is the degree of a hypersimple set ⇔ a is c.e. and a′ = 0′′ . Theorem (R. Robinson 8). Let b and c be c.e. degrees such that c < b and c is low. Then there exist incomparable low c.e. degrees 0 a and a1 , such that 0 1 b = a ∪ a and a > c i , for i < 2 . Griffiths (3) proved that there is a low c.e. T-degree u such that if v is a c.e. T-degree and u ≤ v then v is not completely mitotic. In this article it is proved the following theorem: Theorem. There exists a low c.e. T-degree u such that if v is a c.e. T-degree and u ≤ v then v contains hypersimple wtt -mitotic set, which is not tt -mitotic. From the abovementioned theorems of Martin and R. Robinson follows that it is impossible to replace hypersimple by hyperhypersimple.

Keywords: computably enumerable (c.e.) set, mitotic, wtt -reducibility, tt -reducibility, hypersimple set, low degree.

ACM Classification Keywords: F. Theory of Computation, F.1.3 Complexity Measures and Classes.

Link:

ON HYPERSIMPLE wtt -MITOTIC SETS, WHICH ARE NOT tt -MITOTIC

Arsen H. Mokatsian

http://www.foibg.com/ijita/vol17/ijita17-3-p02.pdf