…
comment: The repository administrator has not yet configured an RDF license.
primary topic: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties

On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties
type: Article
abstract: In this thesis, we give contributions to topics which are related to array noncomputable (a.n.c.) Turing degrees, maximal pairs and to simplicity properties. The outline is as follows. In Chapter 2, we introduce a subclass of the a.n.c. Turing degrees, the so called completely array noncomputable (c.a.n.c. for short) Turing degrees. Here, a computably enumerable (c.e.) Turing degree a is c.a.n.c. if any c.e. set A ∈ a is weak truth-table (wtt) equivalent to an a.n.c. set. We show in Section 2.3 that these degrees exist (indeed, there exist infinitely many low c.a.n.c. degrees) and that they cannot be high. Moreover, we apply some of the ideas used to show the existence of c.a.n.c. Turing degrees to show the stronger result that there exists a c.e. Turing degree whose c.e. members are halves of maximal pairs in the c.e. computably Lipschitz (cl) degrees, thereby solving the first part of the first open problem given in the paper by Ambos-Spies, Ding, Fan and Merkle [ASDFM13]. In Chapter 3, we present an approach to extending the notion of array noncomputability to the setting of almost-c.e. sets (these are the sets which correspond to binary representations of left-c.e. reals). This approach is initiated by the Heidelberg Logic Group and it is worked out in detail in an upcoming paper by Ambos-Spies, Losert and Monath [ASLM18], in the thesis of Losert [Los18] and in [ASFL+]. In [ASLM18], the authors introduce the class of sets with the universal similarity property (u.s.p. for short; throughout this thesis, sets with the u.s.p. will shortly be called u.s.p. sets) which is a strong form of array noncomputability in the setting of almost-c.e. sets and they show that sets with this property exist precisely in the c.e. not totally ω-c.e. degrees. Then it is shown that, using u.s.p. sets, one obtains a simplified method for showing the existence of almost-c.e. sets with a property P (for certain properties P) that are contained in c.e. not totally ω-c.e. degrees, namely b…
date: 2019
author list: authors
type: EPrint
type: DoctoralThesisEPrint
is part of: repository
has document: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (PDF)
has document: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (Other)
subject: 510 Mathematik

On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (PDF)
type: Document
has file: ThesisMonath.pdf
has part: ThesisMonath.pdf

Martin Monath
type: Person
given name: Martin
family name: Monath

On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (Other)
type: Document
is version of: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (PDF)
is volatile version of: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (PDF)
is index codes version of: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties (PDF)
has file: indexcodes.txt
has part: indexcodes.txt

HTML Summary of #27280 On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties
format: text/html
primary topic: On Array Noncomputable Degrees, Maximal Pairs and Simplicity Properties

510 Mathematik
type: Concept
preferred label: 510 Mathematics @en