Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Languages, Structures, and Theories Read chapter Read first chapter

2024 | OriginalPaper | Chapter

12. Turing Reducibility

Author : David Marker

Published in: An Invitation to Mathematical Logic

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Turing reducibility is introduced as a notion of relative complexity and we study the relationship between the arithmetic hierarchy and the jump operator. Several advanced constructions in computability are surveyed, including the construction of incomparable sets, minimal degrees, and an incomplete non-computable computably enumerable set.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Computably Enumerable and Arithmetic Sets
next chapter Gödel’s Incompleteness Theorems
Footnotes
1
By a “nice listing” we mean that we can easily figure out what \(P_e\) is from index e, that all programs are listed and that there is a universal program Q that if we run Q with oracle A in input \((e,\overline x)\) the output is the same as if we ran \(P_e\) with oracle A on input \(\overline x\).
 
2
One might wonder if \(0^{(\omega )}\) is the least upper bound for \(0^\prime , 0^{\prime \prime },\dots \), but Sacks proved that there is X such that \(0^{(n)}<_TX\) for all X, but \(X^{\prime \prime }\equiv _T 0^{(\omega )}\), see [85] 3.3.
 
3
When no confusion arises, we will identify sets and their characteristic functions and write things like \(\bigcup \sigma _i=A.\)
 
4
Friedberg’s work in computability theory was done, while he was an undergraduate. He later went on to become a theoretical physicist.
 
5
If \(\mathcal C \) is a collection of subsets of \(2^{\mathbb N}\) and \(X\subset 2^{\mathbb N}\), we say that X is a basis for \(\mathcal C\) if \(Y\cap X\ne \emptyset \) for all \(Y\in \mathcal C\). The Low Basis Theorem asserts that the low sets are a basis for the collection of sets of paths through computable trees.
 
6
Alternatively, we could make sure that for each tree \(T_n\), there is \(\sigma _n\) with \(|\sigma _n|\ge n\) such that \([T_n]\subseteq N_{\sigma _n}\). In which case \(f=\bigcup \sigma _n\) is the unique element of \([T_n]\).
 
7
Though the solution to Hilbert’s tenth problem tells us that there is \(p(X,\overline Y)\in {\mathbb Z}[X,\overline Y]\) such that \(\{n:{\mathbb N}\models \exists \overline y \ p(n,\overline y)=0\}\) is of intermediate degree. So far, no naturally arising Diophantine equation has this property.
 
8
If \(\mathcal {M}\) is a countable model of ZFC and \(\mathcal D\) is the collection of dense subsets of P that are in the model \(\mathcal {M}\), we call g a Cohen real over \(\mathcal {M}\). Adding Cohen reals to a model of ZFC is the key idea to Cohen’s proof of the independence of the Continuum Hypothesis.
 
Literature
38.
Jech, T.: Set Theory. Springer Monographs in Mathematics. Springer, Berlin (2003)
40.
Jockusch, C., Soare, R.: \(\varPi ^0_1\)-classes classes and degrees of theories. Trans. Am. Math. Soc. 173, 33–56 (1972)
70.
Monin, B., Patey, L.: Turing degrees/Algorithmic Randomness/Reverse Mathematics/Higher Computability Theory. (in preparation)
85.
Sacks, G.: Forcing with perfect closed sets. In: Axiomatic Set Theory Part I, pp. 331–355. Proceedings of Symposia in Pure Mathematics, XIII, Part I. American Mathematical Society, Providence (1971)
95.
Soare, R.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, Berlin (1987)
Metadata
Title
Turing Reducibility
Author
David Marker
Copyright Year
2024
Book
An Invitation to Mathematical Logic

Print ISBN: 978-3-031-55367-7

Electronic ISBN: 978-3-031-55368-4

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-55368-4_12

Premium Partner

    Image Credits