Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Cameo of a Consummate Computabilist Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets

verfasst von : Klaus Ambos-Spies

Erschienen in: Computability and Complexity

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce and discuss some techniques designed for the study of the strongly bounded Turing degrees of the computably enumerable sets, i.e., of the computable Lipschitz degrees and of the identity bounded Turing degrees of c.e. sets. In particular we introduce some tools which allow the transfer of certain facts on the weak truth-table degrees to these degree structures. Using this approach we show that the first order theories of the partial orderings \((\mathrm {R}_\mathrm {cl},\le )\) and \((\mathrm {R}_\mathrm {ibT},\le )\) of the c.e. \(\mathrm {cl}\)- and \(\mathrm {ibT}\)-degrees are not \(\aleph _0\)-categorical and undecidable. Moreover, various other results on the structure of the partial orderings \((\mathrm {R}_\mathrm {cl},\le )\) and \((\mathrm {R}_\mathrm {ibT},\le )\) are obtained along these lines.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Nondensity of Double Bubbles in the D.C.E. Degrees
Nächstes Kapitel Permutations of the Integers Induce only the Trivial Automorphism of the Turing Degrees
Literatur
1.
Ambos-Spies, K.: Cupping and noncapping in the r.e. weak truth-table and Turing degrees. Arch. Math. Logik Grundlag. 25(3–4), 109–126 (1985)MathSciNetCrossRefMATH
2.
Ambos-Spies, K.: On the strongly bounded Turing degrees of simple sets. Logic Comput. Hierarchies Ontos Math. Log. 4, 23–78 (2014). De Gruyter, BerlinMathSciNetMATH
3.
Ambos-Spies, K., Bodewig, P., Fan, Y., Kräling, T.: The partial orderings of the computably enumerable ibT-degrees and cl-degrees are not elementarily equivalent. Ann. Pure Appl. Logic 164(5), 577–588 (2013)MathSciNetCrossRefMATH
4.
Ambos-Spies, K., Bodewig, Thorsten, P., Liang, Y.: Nondistributivity in the strongly bounded Turing degrees of c.e. sets. (to appear)
5.
Ambos-Spies, K., Ding, D., Fan, Y., Merkle, W.: Maximal pairs of computably enumerable sets in the computably Lipschitz degrees. Theory Comput. Syst. 52(1), 2–27 (2013)MathSciNetCrossRefMATH
6.
Ambos-Spies, K., Soare, R.I.: The recursively enumerable degrees have infinitely many one-types. Ann. Pure Appl. Logic 44(1–2), 1–23 (1989)MathSciNetCrossRefMATH
7.
Barmpalias, G.: Computably enumerable sets in the solovay and the strong weak truth table degrees. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 8–17. Springer, Heidelberg (2005). doi:10.​1007/​11494645_​2 CrossRef
8.
Barmpalias, G., Downey, R., Greenberg, N.: Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees. Trans. Amer. Math. Soc. 362(2), 777–813 (2010)MathSciNetCrossRefMATH
9.
Barmpalias, G., Lewis, A.E.M.: The ibT degrees of computably enumerable sets are not dense. Ann. Pure Appl. Logic 141(1–2), 51–60 (2006)MathSciNetCrossRefMATH
10.
11.
12.
Day, A.R.: The computable Lipschitz degrees of computably enumerable sets are not dense. Ann. Pure Appl. Logic 161(12), 1588–1602 (2010)MathSciNetCrossRefMATH
13.
Downey, R.G.: \(\Delta ^0_2\) degrees and transfer theorems. Illinois J. Math. 31(3), 419–427 (1987)MathSciNetMATH
14.
Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, New York (2010)CrossRefMATH
15.
Downey, R.G., Hirschfeldt, D.R., Forte, G.: Randomness and reductibility. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 316–327. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44683-4_​28 CrossRef
16.
17.
Downey, R.G., Lempp, S.: Contiguity and distributivity in the enumerable Turing degrees. J. Symbolic Logic 62(4), 1215–1240 (1997)MathSciNetCrossRefMATH
18.
Downey, R.G., Stob, M.: Structural interactions of the recursively enumerable T- and w-degrees. Special Issue: Second Southeast Asian Logic Conference, Bangkok (1984). Ann. Pure Appl. Logic 31(2–3), 205–236 (1986)MathSciNetCrossRefMATH
19.
Fan, Y., Lu, H.: Some properties of \(sw\)-reducibility. J. Nanjing Univ. (Mathematical Biquarterly) 2, 244–252 (2005)MathSciNetMATH
20.
Fan, Y., Yu, L.: Maximal pairs of c.e. reals in the computably Lipschitz degrees. Ann. Pure Appl. Logic 162(5), 357–366 (2011)MathSciNetCrossRefMATH
21.
Jockusch, C.G.: Three easy constructions of recursively enumerable sets. In: Lerman, M., Schmerl, J.H., Soare, R.I. (eds.) Logic Year 1979–80. LNM, vol. 859, pp. 83–91. Springer, Heidelberg (1981). doi:10.​1007/​BFb0090941 CrossRef
22.
Ladner, R.E., Sasso Jr., L.P.: The weak truth table degrees of recursively enumerable sets. Ann. Math. Logic 8(4), 429–448 (1975)MathSciNetCrossRefMATH
23.
Lempp, S., Nies, A.: The undecidability of the \(\Pi _4\)-theory for the r.e. wtt and Turing degrees. J. Symbolic Logic 60(4), 1118–1136 (1995)MathSciNetCrossRefMATH
24.
25.
André, N.: Computability and Randomness. Oxford University Press, Oxford (2009)MATH
26.
Odifreddi, P.G.: Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, vol. 2. North-Holland Publishing Co., Amsterdam (1999)MATH
27.
Soare, R.I.: Recursively Enumerable Sets and Degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Springer, Berlin (1987)CrossRefMATH
28.
29.
30.
Metadaten
Titel
On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets
verfasst von
Klaus Ambos-Spies
Copyright-Jahr
2017
Buch
Computability and Complexity

Print ISBN: 978-3-319-50061-4

Electronic ISBN: 978-3-319-50062-1

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-50062-1_34