…
comment: The repository administrator has not yet configured an RDF license.
primary topic: Multiple Permitting and Bounded Turing Reducibilities

Multiple Permitting and Bounded Turing Reducibilities
type: Article
abstract: We look at various properties of the computably enumerable (c.e.) not totally ω-c.e. Turing degrees. In particular, we are interested in the variant of multiple permitting given by those degrees. We define a property of left-c.e. sets called universal similarity property which can be viewed as a universal or uniform version of the property of array noncomputable c.e. sets of agreeing with any c.e. set on some component of a very strong array. Using a multiple permitting argument, we prove that the Turing degrees of the left-c.e. sets with the universal similarity property coincide with the c.e. not totally ω-c.e. degrees. We further introduce and look at various notions of socalled universal array noncomputability and show that c.e. sets with those properties can be found exactly in the c.e. not totally ω-c.e. Turing degrees and that they guarantee a special type of multiple permitting called uniform multiple permitting. We apply these properties of the c.e. not totally ω-c.e. degrees to give alternative proofs of well-known results on those degrees as well as to prove new results. E.g., we show that a c.e. Turing degree contains a left-c.e. set which is not cl-reducible to any complex left-c.e. set if and only if it is not totally ω-c.e. Furthermore, we prove that the nondistributive finite lattice S7 can be embedded into the c.e. Turing degrees precisely below any c.e. not totally ω-c.e. degree. We further look at the question of join preservation for bounded Turing reducibilities r and r′ such that r is stronger than r′. We say that join preservation holds for two reducibilities r and r′ if every join in the c.e. r-degrees is also a join in the c.e. r′-degrees. We consider the class of monotone admissible (uniformly) bounded Turing reducibilities, i.e., the reflexive and transitive Turing reducibilities with use bounded by a function that is contained in a (uniformly computable) family of strictly increasing computable functions. This class contains for example i…
date: 2018
author list: authors
type: EPrint
type: DoctoralThesisEPrint
is part of: repository
has document: Multiple Permitting and Bounded Turing Reducibilities (PDF)
has document: Multiple Permitting and Bounded Turing Reducibilities (Other)
subject: 004 Informatik
subject: 510 Mathematik

Multiple Permitting and Bounded Turing Reducibilities (PDF)
type: Document
has file: diss.pdf
has part: diss.pdf

Losert Nadine
type: Person
given name: Losert
family name: Nadine

Multiple Permitting and Bounded Turing Reducibilities (Other)
type: Document
is version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
is volatile version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
is index codes version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
has file: indexcodes.txt
has part: indexcodes.txt

Multiple Permitting and Bounded Turing Reducibilities (Other)
type: Document
is version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
is volatile version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
islightbox thumbnail version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
has file: lightbox.jpg
has part: lightbox.jpg

Multiple Permitting and Bounded Turing Reducibilities (Other)
type: Document
is version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
is volatile version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
ispreview thumbnail version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
has file: preview.jpg
has part: preview.jpg

Multiple Permitting and Bounded Turing Reducibilities (Other)
type: Document
is version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
is volatile version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
ismedium thumbnail version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
has file: medium.jpg
has part: medium.jpg

Multiple Permitting and Bounded Turing Reducibilities (Other)
type: Document
is version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
is volatile version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
issmall thumbnail version of: Multiple Permitting and Bounded Turing Reducibilities (PDF)
has file: small.jpg
has part: small.jpg

HTML Summary of #24241 Multiple Permitting and Bounded Turing Reducibilities
format: text/html
primary topic: Multiple Permitting and Bounded Turing Reducibilities

004 Informatik
type: Concept
preferred label: 004 Data processing Computer science @en

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