D:\TeX_522\01_MOK.DVI


Mathematical Problems of Computer Science 52, 7{13, 2019.

On I nitial Segments of T ur ing Degr ees Containing

Simple T -M itotic but not wtt-M itotic Sets

A r s e n H . Mo ka t s ia n

Institute for Informatics and Automation Problems of NAS RA

e-mail: arsenmokatsian@gmail.com

Abstract

We consider the properties of computably enumerable (c.e.) Turing degrees con-
taining sets, which possess the property of a T -mitotic splitting but don't have a
wtt-mitotic splitting.

It is proved that for any noncomputable c.e. degree b there exists a degree a, such
that a · b and a contains a simple T -mitotic set, which is not wtt-mitotic.

Keywords: Mitotic set, T -reducibility, wtt-reducibility, Simple set, Contiguous
degree.

1 . In t r o d u c t io n

W e s h a ll u s e t h e n o t io n s a n d t e r m in o lo g y in t r o d u c e d in S o a r e [1 ], R o g e r s [2 ].
N o t a t io n s .

W e d e a l wit h s e t s a n d fu n c t io n s o ve r t h e n o n n e g a t ive in t e g e r s ! = f 0 ; 1 ; 2 ; : : :g.
L e t !ev = fx : ( 9k ) ( x = 2 k ) g; !od = fx : ( 9k ) ( x = 2 k + 1 ) g.
L e t 'e b e t h e e

th p a r t ia l c o m p u t a b le fu n c t io n in t h e s t a n d a r d lis t in g ( S o a r e [1 , p . 1 5 ,
p . 2 5 ]) .

If A µ ! a n d e 2 !, le t ©Ae ( x ) = ©e ( A : x) = fegA ( x) ( s e e S o a r e [1 , p p . 4 8 -5 0 ]) .
ÂA d e n o t e s t h e c h a r a c t e r is t ic fu n c t io n o f A, wh ic h is o ft e n id e n t i¯ e d wit h A a n d wr it t e n

s im p ly a s A ( x) .
L e t '( x) # d e n o t e s t h a t '( x ) is d e ¯ n e d , '( x) " d e n o t e s t h a t '( x ) is u n d e ¯ n e d .
We = dom 'e = fx : 'x ( x ) #g.
'e; at s+1 ( x ) # d e n o t e s 'e; s+1 ( x ) # & 'e; s ( x ) ".
x 2 We;at s+1 d e n o t e s x 2 We;s+1 ¡ We;s.
In t h e lit e r a t u r e , Tu r in g r e d u c ib ilit y is u s u a lly t a ke n a s t h e m a in r e d u c ib ilit y. If t h e wo r d

\ r e d u c ib ilit y" is u s e d wit h o u t a fu r t h e r e xp la n a t io n , it m e a n s , a s a r u le , Tu r in g r e d u c ib ilit y.
If t h e t e r m \ d e g r e e o f u n s o lva b ilit y" is u s e d wit h o u t a fu r t h e r e xp la n a t io n , t h e T -d e g r e e is
u s u a lly m e a n t .

De¯nition 1: Th e use function u ( A; e; x; s) is 1 + ( t h e m a xim u m n u m b e r u s e d in c o m p u t a -
t io n if ©Aes ( x ) # ) , a n d = 0 , o t h e r wis e . Th e u s e fu n c t io n u ( A; e; x) is u ( A; e; x; s) if ©Aes ( x ) #
fo r s o m e s, a n d is u n d e ¯ n e d if ©Aes ( x ) ".

7



8 On Initial Segments of Turing Degrees Containing Simple T -Mitotic but not wtt-Mitotic Sets

De¯nition 2: A is computable in (Turing reducible to) B, wr it t e n A·T B, if A = ©Be fo r
s o m e e ( S o a r e [1 , p . 5 0 ]) .

De¯nition 3: A is weak truth-table reducible to B, wr it t e n A ·wtt B, if ( 9e) [A = ©Be & ( 9
c o m p u t a b le f ) ( f ( x ) ¸ u( B; e; x ) ) ] ( wh e r e u ( B; e; x ) is t h e u s e fu n c t io n fr o m D e ¯ n it io n 1 )
( R o g e r s [2 , p . 1 5 8 ]) .

De¯nition 4: If A is a n o n c o m p u t a b le c o m p u t a b ly e n u m e r a b le ( c .e .) s e t , t h e n a splitting
of A is a p a ir A1, A2 o f d is jo in t c .e . s e t s s u c h t h a t A1

S
A2 = A ( D o wn e y , S t o b [3 , p . 4 ]) .

De¯nition 5: C.e . s e t A is T -mitotic (wtt-mitotic), if t h e r e is a s p lit t in g A1, A2 o f A s u c h
t h a t A1 ´T A2 ´T A ( A1 ´wtt A2 ´wtt A) ( D o wn e y , S t o b [3 , p . 8 3 ]) .

De¯nition 6: ( i) A s e t is immune, if it is in ¯ n it e b u t c o n t a in s n o in ¯ n it e c .e . s e t .
( ii) A s e t is simple, if A is c .e . a n d ¹A is im m u n e ( S o a r e [1 , p . 7 8 ]) .

De¯nition 7: A c .e . d e g r e e a is contiguous if fo r e ve r y p a ir A; B o f c .e . s e t s in a, A ´wtt B
( D o wn e y, S t o b [3 , p . 4 5 ]) .

N o t e t h a t e a c h c o n t ig u o u s d e g r e e , b y d e ¯ n it io n , d o e s n 't c o n t a in T -m it o t ic s e t s , wh ic h
a r e n o t wtt-m it o t ic .

L a c h la n p r o ve d t h e e xis t e n c e o f n o n m it o t ic c .e . s e t ( L a c h la n [4 ]) .
L a d n e r p r o ve d t h e e xis t e n c e o f c o m p le t e ly m it o t ic c .e . d e g r e e ( L a d n e r [5 ]) .
L a d n e r a n d S a s s o [6 ] p r o ve d , t h a t fo r e ve r y n o n z e r o c .e . d e g r e e b t h e r e is a n o n z e r o c .e .

d e g r e e a · b s u c h t h a t a is c o n t ig u o u s ( s e e a ls o D o wn e y, S t o b [3 ]) .
Th u s , t h e r e is a n in ¯ n it e c la s s o f c o n t ig u o u s d e g r e e s , a n d t h e s e d e g r e e s , a s we h a ve m e n -

t io n e d , d o n 't c o n t a in T -m it o t ic s e t s , wh ic h a r e n o t wtt-m it o t ic .]
In g r a s s ia ( [7 ]) p r o ve d t h e d e n s it y o f n o n m it o t ic c .e . s e t s ( in R ) ( s e e a ls o D o wn e y, S la -

m a n [8 ]) .
E . J. Gr i± t h s ( [9 ]) p r o ve d t h e fo llo win g Th e o r e m : Th e r e e xis t s a lo w c .e . d e g r e e u s u c h

t h a t if v is a c .e . d e g r e e a n d u · v, t h e n v is n o t c o m p le t e ly m it o t ic .

2 . P r e lim in a r ie s , B a s ic Mo d u le s

T heor em 1: F or any noncomputable c.e. degree b there is a degree a such that a · b and
a contains a simple T -mitotic, but not wtt-mitotic set.

Proof. ( s ke t c h ) L e t h b e a g e n e r a l c o m p u t a b le fu n c t io n t h a t m a p s ! t o !2. L e t ( ªi; Ãi )
d e n o t e s t h e p a ir ( ©i0; 'i0 ) fo r a ll i, wh e r e h( i ) = ( i0; i1 ) ( n o t e t h a t ªi is wtt-r e d u c t io n wit h
Ãi, d e n o t in g t h e c o r r e s p o n d in g u s e fu n c t io n ) .

It is kn o wn ( L a d n e r [1 0 ]) t h a t t h e c o m p u t a b ly e n u m e r a b le s e t A is T -m it o t ic , , A is
T -a u t o r e d u c ib le , a n d s im ila r ly, t h e c o m p u t a b ly e n u m e r a b le s e t A is wtt-m it o t ic , , A is
wtt-a u t o r e d u c ib le ( D o wn e y, S t o b [3 ], s e e a ls o Tr a kh t e n b r o t [1 1 ]) .

Th e r e fo r e , in o r d e r t o a c h ie ve n o n -wtt-m it o t ic it y, it is e n o u g h fo r u s t o a c h ie ve n o n -wtt-
a u t o r e d u c ib ilit y.

Th u s , t o p r o ve o u r t h e o r e m , it is n e c e s s a r y t o c o n s t r u c t s u c h a c .e . s e t A, s o t h a t t h e
fo llo win g r e qu ir e m e n t s a r e m e t .



A. Mokatsian 9

Re : ( 9 x ) : ( ªe ( A
Sfxg; x ) = A ( x ) ) , if ( 8z · y ) ( Ãe ( z ) #) .

Pe : ( We is in ¯ n it e ) ) ( 9 x ) ( x 2 We & x 2 A ) .
N o t e t h a t s a t is fyin g t h e Re r e qu ir e m e n t ( fo r a ll e ) p r o vid e s t h e in ¯ n it y o f t h e s e t ¹A.
Or d e r t h e r e qu ir e m e n t s in t h e fo llo win g p r io r it y r a n kin g : R0; P0; R1; P1; : : : ; Rn; Pn; : : :
L e t l ( e; s) = m a xfx : ( 8y < x) ( ªe;s ( As

Sfyg : y ) = A ( y ) & ( 8z · x) ( ªe ( z ) #) ) g.
Th e m a in s t r a t e g y fo r s a t is fyin g Re is t h e fo llo win g : we s e le c t a n u m b e r ( t h e s o -c a lle d
fo llo we r ) x ( wh ic h s h o u ld b e a c c o m p a n ie d b y t wo m o r e e le m e n t s x¡ 2 a n d x¡ 1 , a n d p o s s ib ly,
t h e t h ir d - x̂; a n e xa c t d e ¯ n it io n o f t h e a t t e n d a n t n u m b e r s o f t h e fo llo we r x, n a m e ly ( x ¡ 2 ) ,
( x ¡ 1 ) , x̂, will b e g ive n h e r e in a ft e r ) , we wa it u n t il l ( e; s) > x a n d e n u m e r a t e x in As+1, if
( 8z < x ) ( Ãe;s ( z ) # ) , s e t t in g r ( e; s + 1 ) = u ( x; e; s) , wh e r e u ( x; e; s) = u ( ªe;s ( As

Sfxg; x) ) .
A n B-p e r m it t in g p r o c e d u r e is in t r o d u c e d in o r d e r t o p r o vid e A·T B ( wh e r e B is a c .e . s e t
fr o m d e g r e e b) .
To s a t is fy t h e r e qu ir e m e n t o f Re a t e a c h s t a g e , we h a ve a ¯ n it e s e t o f fo llo we r s x1;s; < : : : <
xn;s. In t h is c o n s t r u c t io n , a m o d ī c a t io n o f t h e B-p e r m it t in g m e t h o d is u s e d . W e t r e a t t h e
in t e r va l [0 , . . . , i] a s a llo win g fo r xi;s.
To s a t is fy t h e r e qu ir e m e n t o f Pe a t e a c h s t a g e , we h a ve a ¯ n it e s e t o f fo llo we r s y1;s; < : : : <
yn;s. Fo r r e qu ir e m e n t Pe, t h e u s u a l B-p e r m it t in g m e t h o d is u s e d .
Th e c o n s t r u c t io n will b e s u c h t h a t if e ve n t u a lly we h a ve ªe ( A

S fxg; x) = A( x ) & Ãe is a
t o t a l fu n c t io n , t h e n it will b e p o s s ib le t o c o m p u t e B.
Th e g r o u n d o f s a t is fa c t io n s fo r r e qu ir e m e n t s o f Re a n d Pe will b e g ive n b e lo w.

2 .1  B a s ic Mo d u le fo r Re
Th e fo llo we r s x1;s; : : : ; xn;s s a t is fy t h e fo llo win g r u le s b e lo w.
Appointment. If xi;s is c u r r e n t ly d e ¯ n e d a n d xi+1;s is n o t , t h e n if l ( e; s) > xI;s, d e c la r e xi;s a s
active, a n d s e t xi+1;s+1 = ¹z ( z ¸ s + 2 & ( 9 k ) ( z = 2 k ) ) . S e t ~r ( e; s + 1 ) = m a x( u ( xk;s; e; s) :
k · i) . To g e t a n id e a o f t h e r e s t r ic t io n fu n c t io n ~r ( e; s) , we g ive it s d e ¯ n it io n , a lt h o u g h it is
n o t u s e d in t h e b a s ic m o d u le .
W e s a y t h a t xi;s is superactive, if xi;s ¡ 2 a n d xi;s ¡ 1 b e lo n g t o As.
P ermission. If xi;s is a c t ive a n d i 2 Bat s, t h e n if

( i) ( 9 j > i) [xj;s is s u p e r a c t ive & xj;s =2 As], le t j0 = ¹z [xz;s is s u p e r a c t ive & xj;s =2 As].
Th e n we e n u m e r a t e t h e n u m b e r s xj0; s, x̂j0; s in t o As+1 ( wh e r e x̂j0;s = Ãe ( xj0;s ) ) . Ca n c e l
xk;s , fo r a ll ( k > j0 ) . W e will d o t h e s a m e wit h t h e a c c o m p a n yin g e le m e n t s o f t h e
c o r r e s p o n d in g fo llo we r s .

( ii) if ( i) a n d ( :9 j ) [xj;s 2 As] d o e s n o t h o ld , t h e n we e n u m e r a t e t h e n u m b e r s xi;s¡ 2 ; xi;s¡ 1
in t o As+1. Ca n c e l xk;s , fo r a ll ( k > i ) . W e will d o t h e s a m e wit h t h e a c c o m p a n yin g
e le m e n t s o f t h e c o r r e s p o n d in g fo llo we r s .

Fo r a n y i s u c h t h a t t h e fo llo we r xi;s is n o t c a n c e le d a t t h e e n d o f t h e p a r t \ p e r m is s io n " o f t h e
b a s ic m o d u le a n d is a c t ive , le t 's s e t xi;s+1 = xi;s. W e will d o t h e s a m e wit h t h e a c c o m p a n yin g
e le m e n t s o f t h e c o r r e s p o n d in g fo llo we r s .

Th e \ c a n c e lla t io n " r u le , wh ic h is p r e s e n t in t h e p r o o f o f Th e o r e m 4 .8 ( D o wn e y, S la -
m a n [8 ]) , in t h is c a s e it will b e n e c e s s a r y t o n o t e t h e e ®e c t o f t h e r e qu ir e m e n t s o f Rj a n d Pj
( wh e r e j < e) o n s a t is fyin g t h e r e qu ir e m e n t Re, b u t n o t t o d e s c r ib e t h e b a s ic m o d u le it s e lf
fo r Re.



1 0 On Initial Segments of Turing Degrees Containing Simple T -Mitotic but not wtt-Mitotic Sets

2 .2  B a s ic Mo d u le fo r Pe
Th e fo llo we r s y1;s; : : : ; yn;s s a t is fy t h e fo llo win g r u le s b e lo w.
Appointment. If yi;s is c u r r e n t ly d e ¯ n e d a n d yi+1;s is n o t , t h e n if ( 9z ) ( z 2 We z ¸ yi;s ) ,
d e c la r e yi;s a s a c t ive , a n d s e t yi+1;s+1 = ¹z ( z ¸ s & ( 9 k ) ( z = 2 k ) ) .
P ermission. If yi;s is a c t ive a n d i 2 Bat s, t h e n e n u m e r a t e t h e n u m b e r s yi;s; yi;s + 1 ; z a n d
z + 1 in t o As+1.

Th e \ c a n c e lla t io n " r u le , wh ic h is p r e s e n t in t h e p r o o f o f Th e o r e m 4 .8 ( D o wn e y, S la -
m a n [8 ]) , in t h is c a s e it will b e n e c e s s a r y t o n o t e t h e e ®e c t o f t h e r e qu ir e m e n t s o f Rj ( wh e r e
j · e ) o n s a t is fyin g t h e r e qu ir e m e n t Pe, b u t n o t t o d e s c r ib e t h e b a s ic m o d u le it s e lf fo r Pe.

3 . V e r ī c a t io n o f L e m m a s

Lemma 1: Suppose that Ãe is total and ( 8x ) ( ªe ( A
S fxg; x ) #) .

Then ( 9 y ) : ( ( ªe ( A
S fyg; y ) = A ( y ) ) . Thus, the requirement Re is satis¯ed.

Proof. S u p p o s e o t h e r wis e . W e s h o w t h a t B is c o m p u t a b le .
N o t e t h a t s in c e we o n ly c o n s id e r t h e s a t is fa c t io n o f t h e b a s is m o d u le fo r Re ( t h a t is , we

d o n o t t a ke in t o a c c o u n t t h e e ®e c t o f t h e r e qu ir e m e n t s Rj a n d Pj ( wh e r e j < e) o n t h e
s a t is fa c t io n o f t h e r e qu ir e m e n t Re ) , it is o b vio u s t h a t c o n d it io n s ( i) , ..., ( iv) a r e m e t .

( i) A ll t h e xi;s e ve n t u a lly b e c o m e p e r m a n e n t ly d e ¯ n e d , t h a t is lim s xi;s = xi e xis t s wit h
xi =2 A.

( ii) On c e xk is d e ¯ n e d a t s t a g e t, ( 8s > t ) ( u ( xk; e; t ) = u ( xk; e; s) = u( e; xk ) ) .

( iii) ( 8i ) ( xi+1 > m a xfu( e; xk ) : k · i g) .

( iv) It c a n b e e ®e c t ive ly r e c o g n iz e d , wh e n ( i) o c c u r s .

Two c a s e s a r e p o s s ib le :

( a ) ( 9 m) ( 8 k > m ) [xk ¡ 2 =2 A];

( b ) ( 8 m) ( 9 k > m ) [xk ¡ 2 2 A].

Fo r b o t h c a s e s ( ( a ) a n d ( b ) ) , it will b e p r o ve d t h a t B is c o m p u t a b le ( a n d t h u s , t h e
a s s u m p t io n t h a t L e m m a 1 is fa ls e will le a d t o a c o n t r a d ic t io n wit h t h e s u p p o s it io n o f n o n -
c o m p u t a b ilit y o f B ) .

N o w, if ( a ) h o ld s , we p r o ve t h a t B is c o m p u t a b le .
If c o n d it io n s ( i) , ..., ( iv) a r e s a t is ¯ e d , we s h o w h o w t o c o m p u t e B ( t h a t is , t h e c h a r a c -

t e r is t ic fu n c t io n o f t h e s e t B; r e m in d t h a t we o ft e n id e n t ify t h e s e t B wit h it s c h a r a c t e r is t ic
fu n c t io n ) .

L e t f k x d e n o t e s t h e r e s t r ic t io n o f f t o a r g u m e n t s y < x, a n d A k x d e n o t e s ÂA k x.
L e t s0 b e s u c h a s t a g e t h a t B k m + 1 = Bs0 k m + 1 a n d A k xm+1 = As0 k xm+1.
L e t q 2 ! a n d q > m. E ®e c t ive ly c o m p u t e a s t a g e s s o t h a t xq+1 is d e ¯ n e d , t h a t is

xq+1 = xq+1;s ( in t h a t c a s e , in fa c t , s > s0 ) .
Th e n xq is a c t ive , xq 2 A a n d s in c e xq+1 is t h e ¯ n a l va lu e o f t h e q + 1 -t h fo llo we r , t h e

c o m p u t a t io n s o f u ( xj; e; s) a r e t r u e fo r a ll j · q.
In t h is c a s e q 2 B , q 2 Bs, b e c a u s e o t h e r wis e it wo u ld le a d t o t h e fa c t t h a t xq ¡ 2



A. Mokatsian 1 1

wo u ld h a ve e n t e r e d t h e s e t , c o n t r a r y t o o u r a s s u m p t io n t h a t c a s e ( a ) h o ld s .
N o w s u p p o s e t h a t c a s e ( b ) h o ld s . L e t u s p r o ve t h a t in t h is c a s e a ls o B is c o m p u t a b le .
If c o n d it io n s ( i) , ..., ( iv) a r e fu l̄ lle d , we s h o w h o w t o c o m p u t e B.
L e t q 2 !. E ®e c t ive ly c o m p u t e s u c h a s t a g e s a n d a n u m b e r p s o t h a t p = ¹z ( z ¸ q &

xz¡2 2 A & xz+1 = xz+1;s ) .
Th e n xp is a c t ive , xp =2 As a n d s in c e xp+1 is t h e ¯ n a l va lu e o f t h e p + 1 -t h fo llo we r , t h e n

u ( xj; e; s) c o m p u t a t io n s a r e t r u e fo r a ll j · p. In t h is c a s e q 2 B , q 2 Bs, s in c e o t h e r wis e
( t h a t is , if q e n t e r s B a ft e r t h e s t a g e s) t h is will le a d t o t h e e n t r y p in t o A a n d s a t is fa c t io n
o f t h e r e qu ir e m e n t Re, wh ic h will c o n t r a d ic t t h e in it ia l a s s u m p t io n t h a t L e m m a 1 is fa ls e .

L e m m a 1 is p r o o ve d .

Lemma 2: Suppose that We is an in¯nite set. Then ( 9 z ) ( z 2 We & z 2 A ) . Thus, the
requirement Pe is satis¯ed.

Proof. S u p p o s e o t h e r wis e .
W e s h o w t h a t B is c o m p u t a b le .
L e t ~r ( e) = lim s ~r ( e; s) .
A lt h o u g h t h e u s e o f t h is fu n c t io n in t h e d e s c r ip t io n o f t h e b a s is m o d u le fo r Pe is n o t n e c e s s a r y,
a n in d ic a t io n o f t h is fu n c t io n c le a r ly s h o ws t h e e ®e c t o f t h e r e qu ir e m e n t s Rj ( wh e r e j · e )
o n t h e s a t is fa c t io n o f t h e r e qu ir e m e n t s Pe wh e n c o n s t r u c t in g t h e s e t A.
L e t t0 b e s u c h t h a t ( 8s ¸ t0 ) ~r ( e; s) = ~r ( e ) .
Th e n it is o b vio u s , t h a t a ll t h e yi;s b e c o m e p e r m a n e n t ly d e ¯ n e d ( i.e ., 8i 9 ( t ¸ t0 ) ( 8s) ( yi;t =
yi;s = yi ) ) wit h yi =2 A.
In fa c t , if t h e r e e xis t e d k s u c h t h a t yk 2 A, t h e n , b y c o n s t r u c t io n , t h e r e wo u ld e xis t z s u c h
t h a t z 2 We

T
A.

A s s u m in g t h e o p p o s it e o f t h e s t a t e m e n t o f t h e p r o p o s it io n , we s h o w h o w B c a n b e c o m p u t e d .
L e t q 2 !. Fin d t ¸ t0 s u c h t h a t yq is p e r m a n e n t ly d e ¯ n e d . Th e n q 2 B , q 2 Bt, s in c e
o t h e r wis e q0 s e n t r y in t o B wo u ld m e e t Pe.

L e m m a 2 is p r o o ve d .

4 . Co n c lu s io n

N o t e t h a t t h e c o h e r e n c e o f c o n s t r u c t io n s t o s a t is fy t h e r e qu ir e m e n t s Re a n d Pe ( fo r a ll e) is
n o t d i± c u lt , s in c e s a t is fyin g t h e r e qu ir e m e n t s Re a n d Pe ( fo r a ll e ) r e qu ir e s a ¯ n it e n u m b e r
o f s t e p s . W e a ls o n o t e t h a t t h e in d ic a t e d m e t h o d o f c o n s t r u c t in g t h e s e t A ( b a s e d o n t h e
c o n s t r u c t io n s fo r t h e b a s ic m o d u le s ) will r e s u lt in t h e s e t A

T
!ev b e in g T -e qu iva le n t t o t h e

s e t A
T

!od.
Th e s e r e m a r ks a llo w u s t o c o m p le t e t h e p r o o f o f t h e t h e o r e m .

N o t e t h a t it fo llo ws fr o m t h e a b o ve t h e o r e m t h a t b e lo w a n y n o n c o m p u t a b le c .e . d e g r e e
t h e r e is a n in ¯ n it e n u m b e r o f n o n c o m p u t a b le c .e . d e g r e e s wit h t h e a b o ve m e n t io n e d p r o p e r t y
( s in c e t h e d e g r e e a ( m e n t io n e d in t h e t h e o r e m ) , c o n t a in in g a s im p le s e t , is a n o n c o m p u t a b le
c .e . d e g r e e ) .



1 2 On Initial Segments of Turing Degrees Containing Simple T -Mitotic but not wtt-Mitotic Sets

References

[1 ] R . I. S o a r e , R ecursively E numerable Sets and D egrees, S p r in g e r -V e r la g , 1 9 8 7 .
[2 ] H . R o g e r s , Theory of R ecursive F unctions and E ®ective Computability, Mc Gr a w-H ill

B o o k Co m p a n y, 1 9 6 7 .
[3 ] R . G. D o wn e y a n d M. S t o b , \ S p lit t in g Th e o r e m s In R e c u r s io n Th e o r y" , Ann. P ure

Appl. L ogic, vo l. 6 5 , p p . 1 -1 0 6 , 1 9 9 3 .
[4 ] A . H . L a c h la n , Th e P r io r it y Me t h o d . I, Ze it s c h r ift fr m a t h e m a t is c h e L o g ik u n d Gr u n d -

la g e n d e r Ma t h e m a t ik, vo l. 1 3 , p p . 1 -1 0 , 1 9 6 7 .
[5 ] R . L a d n e r , \ A c o m p le t e m it o t ic r e c u r s ive ly e n u m e r a b le d e g r e e " , Trans. Amer. M ath.

Soc., 1 8 4 , p p . 4 9 7 -5 0 7 , 1 9 7 3 .
[6 ] R . L a d n e r a n d L . S a s s o , \ Th e we a k t r u t h -t a b le d e g r e e s o f r e c u r s ive ly e n u m e r a b le s e t s " ,

Arch. M ath. L ogik Grundlang Grundlagen der M athematik, vo l. 8 , p p . 4 2 9 -4 4 8 , 1 9 7 5 .
[7 ] M. In g r a s s ia , P -generecity for recursive enumerable degrees, P h D . Th e s is , U n ive r s it y o f

Illin o is , 1 9 8 1 .
[8 ] R . G. D o wn e y a n d T. A . S la m a n , \ Co m p le t e ly Mit o t ic R . E . D e g r e e s " , Ann. P ure Appl.

L ogic, vo l. 4 1 , p p . 1 1 9 -1 5 2 , 1 9 8 9 .
[9 ] E . J. Gr i± t h s , Completely M itotic Turing D egrees, J ump Classes and E numeration

D egrees, P h .D . Th e s is , U n ive r s it y o f W is c o n s in -Ma d is o n , 1 9 9 8 .
[1 0 ] R . L a d n e r , \ Mit o t ic R e c u r s ive ly E n u m e r a b le S e t s " , The J ournal of Symbolic L ogic,

vo l. 3 8 , n o . 2 , p p . 1 9 9 -2 1 1 , 1 9 7 3 .
[1 1 ] B . A . Tr a kh t e n b r o t , \ On a u t o r e d u c ib ilit y" ( in R u s s ia n ) , D okl. Akad. Nauk SSSR ,

vo l. 1 9 2 , p p . 1 2 2 4 -1 2 2 7 , 1 9 7 0 .

Submitted 04.07.2019, accepted 22.11.2019.

ä³ñ½ T -ÙÇÃáïÇÏ, µ³Ûó áã wtt-ÙÇÃáïÇÏ µ³½ÙáõÃÛáõÝÝ»ñ
å³ñáõݳÏáÕ ÃÛáõñÇÝ·Û³Ý ³ëïÇ׳ÝÝ»ñÇ áñáß

ѳïÏáõÃÛáõÝÝ»ñÇ í»ñ³µ»ñÛ³É

²ñë»Ý Ð. ØáϳóÛ³Ý

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï

e-mail: arsenmokatsian@gmail.com

²Ù÷á÷áõÙ

лﳽáïíáõÙ»Ý T -ÙÇÃáïÇÏ ïñáÑÙ³Ý Ñ³ïÏáõÃÛ³Ùµ ûÅïí³Í, µ³Ûó wtt-ÙÇÃáïÇÏ
ïñáÑáõÙ ãáõÝ»óáÕ µ³½ÙáõÃÛáõÝÝ»ñ å³ñáõݳÏáÕ é»ÏáõñëÇíáñ»Ý Ãí³ñÏ»ÉÇ (é.Ã.)
ÃÛáõñÇÝ·Û³Ý ³ëïÇ׳ÝÝ»ñÇ Ñ³ïÏáõÃÛáõÝÝ»ñÁ: ²å³óáõóí³Í ¿, áñ Ï³Ù³Û³Ï³Ý áã
é»ÏáõñëÇí (é.Ã.) a ³ëïÇ׳ÝÇ Ñ³Ù³ñ ·áÛáõÃÛáõÝ áõÝÇ áã é»ëáõñëÇí (é.Ã) ³ÛÝåÇëÇ b
³ëïÇ׳Ý, áñ b · a ¨ b-Ý å³ñáõݳÏáõÙ ¿ å³ñ½ T - ÙÇÃáïÇÏ, µ³Ûó áã wtt- ÙÇÃáïÇÏ
µ³½ÙáõÃÛáõÝ:



A. Mokatsian 1 3

´³Ý³ÉÇ µ³é»ñ` ÙÇÃáïÇÏ µ³½ÙáõÃÛáõÝ, T -ѳݷ»óáõÙ, wtt-ѳݷ»óáõÙ, å³ñ½
µ³½ÙáõÃÛáõÝ, ½áõ·³Ïóí³Í ³ëïÇ׳Ý:

Î íåêîòîðûõ ñâîéñòâàõ òüþðèíãîâûõ ñòåïåíåé, ñîäåðæàùèõ
ïðîñòûå T -ìèòîòè÷åñêèå ìíîæåñòâà, íå ÿâëÿþùèåñÿ

wtt-ìèòîòè÷åñêèìè

Àðñåí À. Ìîêàöÿí

Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ
e-mail: arsenmokatsian@gmail.com

Àííîòàöèÿ

Èññëåäóþòñÿ ñâîéñòâà ðåêóðñèâíî ïåðå÷èñëèìûõ (ð.ï.) òüþðèíãîâûõ
ñòåïåíåé, ñîäåðæàùèõ ìíîæåñòâà, êîòîðûå îáëàäàþò ñâîéñòâîì -ìèòîòè÷åñêîãî
ðàçáèåíèÿ, íî íå èìåþò wtt-ìèòîòè÷åñêîãî ðàçáèåíèÿ. Äîêàçàíî, ÷òî äëÿ ëþáîé
íåðåêóðñèâíîé (ð.ï.) ñòåïåíè a ñóùåñòâóåò íåðåêóðñèâíàÿ (ð.ï.) ñòåïåíü b, òàêàÿ
÷òî b · a è b ñîäåðæèò ïðîñòîå T -ìèòîòè÷åñêîå ìíîæåñòâî, êîòîðîå íå ÿâëÿåòñÿ
wtt-ìèòîòè÷åñêèì.

Êëþ÷åâûå ñëîâà: ìèòîòè÷åñêîå ìíîæåñòâî, T -ñâîäèìîñòü, wtt-ñâîäèìîñòü,
ïðîñòîå ìíîæåñòâî, ñöåïëåííàÿ ñòåïåíü.