Menu
Home
Contact us
Stats
Categories
Calendar
Toggle Wiki
Wiki Home
Last Changes
Rankings
List pages
Orphan pages
Sandbox
Print
Toggle Image Galleries
Galleries
Rankings
Toggle Articles
Articles home
List articles
Rankings
Toggle Blogs
List blogs
Rankings
Toggle Forums
List forums
Rankings
Toggle File Galleries
List galleries
Rankings
Toggle Maps
Mapfiles
Toggle Surveys
List surveys
Stats
ITHEA Classification Structure > F. Theory of Computation  > F.1 COMPUTATION BY ABSTRACT DEVICES  > F.1.3 Complexity Measures and Classes
ON HYPERSIMPLE wtt -MITOTIC SETS, WHICH ARE NOT tt -MITOTIC
By: Arsen H. Mokatsian (4453 reads)
Rating: (1.00/10)

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

Print
F.1.3 Complexity Measures and Classes
article: Review of some problems on the complexity of simultaneous divisibility of linear · ON HYPERSIMPLE wtt -MITOTIC SETS, WHICH ARE NOT tt -MITOTIC ·
Login
[ register | I forgot my password ]
World Clock
Powered by Tikiwiki Powered by PHP Powered by Smarty Powered by ADOdb Made with CSS Powered by RDF powered by The PHP Layers Menu System
RSS Wiki RSS Blogs rss Articles RSS Image Galleries RSS File Galleries RSS Forums RSS Maps rss Calendars
[ Execution time: 0.09 secs ]   [ Memory usage: 7.51MB ]   [ GZIP Disabled ]   [ Server load: 0.09 ]
Powered by Tikiwiki CMS/Groupware