<> "The repository administrator has not yet configured an RDF license."^^ . <> . . "On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties"^^ . "In this thesis, we give contributions to topics which are related to array noncomputable\r\n(a.n.c.) Turing degrees, maximal pairs and to simplicity properties. The\r\noutline is as follows. In Chapter 2, we introduce a subclass of the a.n.c. Turing\r\ndegrees, the so called completely array noncomputable (c.a.n.c. for short) Turing\r\ndegrees. Here, a computably enumerable (c.e.) Turing degree a is c.a.n.c. if any\r\nc.e. set A ∈ a is weak truth-table (wtt) equivalent to an a.n.c. set. We show\r\nin Section 2.3 that these degrees exist (indeed, there exist infinitely many low\r\nc.a.n.c. degrees) and that they cannot be high. Moreover, we apply some of the\r\nideas used to show the existence of c.a.n.c. Turing degrees to show the stronger\r\nresult that there exists a c.e. Turing degree whose c.e. members are halves of\r\nmaximal pairs in the c.e. computably Lipschitz (cl) degrees, thereby solving the\r\nfirst part of the first open problem given in the paper by Ambos-Spies, Ding,\r\nFan and Merkle [ASDFM13].\r\nIn Chapter 3, we present an approach to extending the notion of array\r\nnoncomputability to the setting of almost-c.e. sets (these are the sets which\r\ncorrespond to binary representations of left-c.e. reals). This approach is initiated\r\nby the Heidelberg Logic Group and it is worked out in detail in an upcoming\r\npaper by Ambos-Spies, Losert and Monath [ASLM18], in the thesis of Losert\r\n[Los18] and in [ASFL+]. In [ASLM18], the authors introduce the class of sets\r\nwith the universal similarity property (u.s.p. for short; throughout this thesis,\r\nsets with the u.s.p. will shortly be called u.s.p. sets) which is a strong form of\r\narray noncomputability in the setting of almost-c.e. sets and they show that sets\r\nwith this property exist precisely in the c.e. not totally ω-c.e. degrees. Then it\r\nis shown that, using u.s.p. sets, one obtains a simplified method for showing\r\nthe existence of almost-c.e. sets with a property P (for certain properties P)\r\nthat are contained in c.e. not totally ω-c.e. degrees, namely by showing that\r\nu.s.p. sets have property P. This is demonstrated by showing that u.s.p. sets\r\nare computably bounded random (CB-random), thereby extending a result from\r\nBrodhead, Downey and Ng [BDN12]. Moreover, it is shown that the c.e. not\r\ntotally ω-c.e. degrees can be characterized as those c.e. degrees which contain\r\nan almost-c.e. set which is not cl-reducible to any complex almost-c.e. set. This\r\naffirmatively answers a conjecture by Greenberg.\r\nFor the if-direction of the latter result, we prove a new result on maximal\r\npairs in the almost-c.e. sets by showing the existence of locally almost-c.e. sets\r\nwhich are halves of maximal pairs in the almost-c.e. sets such that the second\r\nhalf can be chosen to be c.e. and arbitrarily sparse. This extends Yun Fan’s\r\nresult on maximal pairs [Fan09]. By our result, we also get a new proof of one of\r\nthe main results in Barmpalias, Downey and Greenberg [BDG10], namely that\r\nin any c.e. a.n.c. degree there is a left-c.e. real which is not cl-reducible to any\r\nML-random left-c.e. real.\r\nIn this thesis, we give an overview of some of the results from [ASLM18] and\r\nsketch some of the proofs to illustrate this new methodology and, subsequently,\r\nwe give a detailed proof of the above maximal pair result.\r\nIn Chapter 4, we look at the interaction between a.n.c. wtt-degrees and the\r\nmost commonly known simplicity properties by showing that there exists an\r\na.n.c. wtt-degree which contains an r-maximal set. By this result together with\r\nthe result by Ambos-Spies [AS18] that no a.n.c. wtt-degree contains a dense\r\nsimple set, we obtain a complete characterization which of the classical simplicity\r\nproperties may hold for a.n.c. wtt-degrees.\r\nThe guiding theme for Chapter 5 is a theorem by Barmpalias, Downey and\r\nGreenberg [BDG10] in which they characterize the c.e. not totally ω-c.e. degrees\r\nas the c.e. degrees which contain a c.e. set which is not wtt-reducible to any\r\nhypersimple set. So Ambos-Spies asked what the above characterization would\r\nlook like if we replaced hypersimple sets by maximal sets in the above theorem.\r\nIn other words, what are the c.e. Turing degrees that contain c.e. sets which\r\nare not wtt-reducible to any maximal set. We completely solve this question\r\non the set level by introducing the new class of eventually uniformly wtt-array\r\ncomputable (e.u.wtt-a.c.) sets and by showing that the c.e. sets with this property\r\nare precisely those c.e. sets which are wtt-reducible to maximal sets. Indeed,\r\nthis characterization can be extended in that we can replace wtt-reducible by\r\nibT-reducible and maximal sets by dense simple sets. By showing that the c.e.\r\ne.u.wtt-a.c. sets are closed downwards under wtt-reductions and under the join\r\noperation, it follows that the c.e. wtt-degrees containing e.u.wtt-a.c. sets form\r\nan ideal in the upper semilattice of the c.e. wtt-degrees and, further, we obtain\r\na characterization of the c.e. wtt-degrees which contain c.e. sets that are not\r\nwtt-reducible to any maximal set. Moreover, we give upper and lower bounds\r\n(with respect to ⊆) for the class of the c.e. e.u.wtt-a.c. sets. For the upper bound,\r\nwe show that any c.e. e.u.wtt-a.c. set has array computable wtt-degree. For the\r\nlower bound, we introduce the notion of a wtt-superlow set and show that any\r\nwtt-superlow c.e. set is e.u.wtt-a.c. Besides, we show that the wtt-superlow c.e.\r\nsets can be characterized as the c.e. sets whose bounded jump is ω-computably\r\napproximable (ω-c.a. for short); hence, they are precisely the bounded low sets as\r\nintroduced in the paper by Anderson, Csima and Lange [ACL17]. Furthermore,\r\nwe prove a hierarchy theorem for the wtt-superlow c.e. sets and we show that\r\nthere exists a Turing complete set which lies in the intersection of that hierarchy.\r\nFinally, it is shown that the above bounds are strict, i.e., there exist c.e. e.u.wtta.\r\nc. sets which are not wtt-superlow and that there exist c.e. sets whose wtt-degree\r\nis array computable and which are not e.u.wtt-a.c. (where here, we obtain the\r\nseparation even on the level of Turing degrees). The results from Chapter 5 will\r\nbe included in a paper which is in preparation by Ambos-Spies, Downey and\r\nMonath [ASDM19]."^^ . "2019" . . . . . . . "Martin"^^ . "Monath"^^ . "Martin Monath"^^ . . . . . . "On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (PDF)"^^ . . . "ThesisMonath.pdf"^^ . . . "On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (Other)"^^ . . . . . . "indexcodes.txt"^^ . . "HTML Summary of #27280 \n\nOn Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties\n\n" . "text/html" . . . "510 Mathematik"@de . "510 Mathematics"@en . .