Where join preservation fails in the bounded Turing degrees of c.e. sets
| Autor: | Nadine Losert |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Linear bounded automaton 010102 general mathematics 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Combinatorics Join and meet Computable function Monotone polygon Computational Theory and Mathematics Bounded function 0202 electrical engineering electronic engineering information engineering Join (sigma algebra) Uniform boundedness 020201 artificial intelligence & image processing 0101 mathematics Turing computer Information Systems Mathematics computer.programming_language |
| Zdroj: | Information and Computation. 256:185-195 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2017.07.005 |
| Popis: | We 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 computably enumerable (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 identity bounded Turing (ibT-) and computable Lipschitz (cl-) reducibility. Our main result is that join preservation fails for cl and any strictly weaker monotone admissible uniformly bounded Turing reducibility ( Theorem 10 ). We also look at the dual question of meet preservation and show that for all monotone admissible bounded Turing reducibilities r and r ′ such that r is stronger than r ′ , meet preservation holds. Finally, we completely solve the question of join and meet preservation in the classical reducibilities 1, m, tt, wtt, and T. This is an extended version of our article [18] . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect