www.wikidata.de-de.nina.az

Turinggrad In der Berechenbarkeitstheorie und der mathematischen Logik misst der auch Grad der Unlösbarkeit einer Menge

Turinggrad

In der Berechenbarkeitstheorie und der mathematischen Logik misst der Turinggrad (auch Grad der Unlösbarkeit) einer Menge natürlicher Zahlen die algorithmische Unlösbarkeit der Menge. Das Konzept des Turinggrades ist fundamental in der Berechenbarkeitstheorie, wo Mengen natürlicher Zahlen oft als Entscheidungsprobleme angesehen werden; der Turinggrad einer Menge gibt an, wie schwer das Entscheidungsproblem für die Menge ist.

Zwei Mengen sind Turing-äquivalent, wenn sie den gleichen Grad der Unlösbarkeit haben; jeder Turinggrad ist eine Menge Turing-äquivalenter Mengen, sodass zwei Mengen genau dann in unterschiedlichen Turinggraden liegen, wenn sie nicht Turing-äquivalent sind. Außerdem sind die Turinggrade im folgenden Sinne partiell geordnet: Wenn der Turinggrad einer Menge kleiner als der Turinggrad einer Menge ist, dann kann jede (unberechenbare) Prozedur, die korrekt entscheidet, ob Zahlen in liegen, berechenbar in eine Prozedur umgewandelt werden, die korrekt entscheidet, ob Zahlen in liegen. In diesem Sinne korrespondiert der Turinggrad einer Menge mit dem Grad ihrer algorithmischen Unlösbarkeit.

Die Turinggrade wurden 1944 von Emil Leon Post eingeführt, und viele grundlegende Resultate wurden 1954 von Stephen Cole Kleene und Post bewiesen. Die Turinggrade sind bis heute Gegenstand intensiver Forschung. Viele Beweise in diesem Gebiet benutzen eine Beweistechnik, die als Prioritätsmethode bekannt ist.

Turing-Äquivalenz Bearbeiten

Im Folgenden bezieht sich das Wort Menge auf Teilmengen natürlicher Zahlen. Eine Menge heißt Turing-reduzierbar auf eine Menge , wenn es eine Orakel-Turingmaschine gibt, die mit Hilfe eines Orakels für entscheidet, ob eine gegebene Zahl in liegt. Die Notation steht für: ist auf Turing-reduzierbar.

Zwei Mengen und heißen Turing-äquivalent, wenn sie aufeinander Turing-reduzierbar sind. Die Notation steht für: und sind Turing-äquivalent. Die Relation ist eine Äquivalenzrelation.

Turinggrad Bearbeiten

Ein Turinggrad ist eine Äquivalenzklasse der Relation . Die Notation bezeichnet die Äquivalenzklasse, die die Menge enthält. Die Klasse aller Turinggrade wird mit bezeichnet.

Die Turinggrade haben eine partielle Ordnung . Sie ist so definiert, dass genau dann gilt, wenn . Es gibt einen Turinggrad, der genau die entscheidbaren Mengen enthält, und dieser Grad ist kleiner als alle anderen. Er wird mit (Null) bezeichnet, da er das kleinste Element der partiell geordneten Menge ist. Turinggrade werden meist durch Fettdruck bezeichnet, um sie von Mengen zu unterscheiden. Als Variablen für Turinggrade dienen fette kleine Buchstaben etc.

Für alle Mengen und ist (gesprochen join) die Vereinigung der Mengen und . Der Turinggrad von ist das Supremum der Grade und . Damit ist ein oberer Halbverband. Das Supremum der Grade und wird mit bezeichnet. Es ist bekannt, dass kein Verband ist, da es Paare von Graden ohne Infimum gibt.

Für jede Menge bezeichnet die Menge der Indizes von Orakelmaschinen, die auf ihrem eigenen Index als Eingabe halten, wenn sie als Orakel benutzen. Die Menge wird als Turing-Sprung von bezeichnet. Der Turing-Sprung eines Grades ist der Grad ; dies ist wohldefiniert, da aus folgt. Ein wichtiges Beispiel ist , der Grad des Halteproblems.

Grundlegende Eigenschaften der Turinggrade Bearbeiten

  • Für jeden Grad gilt die strikte Ungleichung .
  • Für jeden Grad ist die Menge der Grade unter höchstens abzählbar. Die Menge der Grade über hat Mächtigkeit .

Struktur der Turinggrade Bearbeiten

Die Struktur der Turinggrade wurde intensiv erforscht. Die folgende Liste gibt nur wenige der vielen bekannten Ergebnisse an. Generell lässt sich aus den bekannten Ergebnissen schließen, dass die Struktur der Turinggrade sehr kompliziert ist.

Ordnungseigenschaften Bearbeiten

  • Es gibt minimale Grade. Ein Grad heißt minimal, wenn ungleich ist und es keinen Grad zwischen und gibt. Damit ist die Ordnung der Grade nicht dicht.
  • Für jeden Grad ungleich gibt es einen Grad , der mit nicht vergleichbar ist.
  • Es gibt untereinander nicht vergleichbare Turinggrade.
  • Es gibt Paare von Graden ohne Infimum. Damit ist kein Verband.
  • Jede abzählbare partielle Ordnung lässt sich in die Turinggrade einbetten.
  • Keine unendliche, strikt aufsteigende Folge von Graden hat ein Supremum.

Eigenschaften des Sprungoperators Bearbeiten

  • Für jeden Grad gibt es einen Grad zwischen und . Es gibt sogar eine abzählbar unendliche Folge paarweise nicht vergleichbarer Grade zwischen und .
  • Ein Grad hat die Form für ein genau dann, wenn gilt.
  • Für jeden Grad gibt es einen Grad , sodass und . Solch ein Grad heißt niedrig relativ zu .
  • Es gibt eine unendliche Folge von Graden, sodass für alle .

Logische Eigenschaften Bearbeiten

  • Shore und Slaman (1999) zeigten, dass sich der Sprungoperator in der Struktur der Grade in der Logik erster Stufe mit der Sprache definieren lässt.

Struktur der rekursiv aufzählbaren Turinggrade Bearbeiten

Dieser endliche Verband kann nicht in die rekursiv aufzählbaren Grade eingebettet werden.

Ein Grad heißt rekursiv aufzählbar, wenn er eine rekursiv aufzählbare Menge enthält. Jeder rekursiv aufzählbare Grad ist kleiner oder gleich , aber nicht jeder Grad kleiner ist rekursiv aufzählbar.

  • (G. E. Sacks, 1964) Die rekursiv aufzählbaren Grade sind dicht, das heißt, zwischen zwei rekursiv aufzählbaren Graden existiert immer ein dritter rekursiv aufzählbarer Grad.
  • (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) Es gibt zwei rekursiv aufzählbare Grade, die kein Infimum in den rekursiv aufzählbaren Graden haben.
  • (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) Es gibt ein Paar von rekursiv aufzählbaren Graden ungleich , deren Infimum ist.
  • (S. K. Thomason, 1971) Jeder endlicher distributiver Verband kann in die rekursiv aufzählbaren Grade eingebettet werden. Es ist sogar möglich, die abzählbare boolesche Algebra ohne Atome so einzubetten, dass Suprema und Infima erhalten bleiben.
  • (A. H. Lachlan and R. I. Soare, 1980) Nicht alle endlichen Verbände können in die rekursiv aufzählbaren Grade eingebettet werden, sodass Suprema und Infima erhalten bleiben. So kann insbesondere der rechts abgebildete Verband nicht eingebettet werden.
  • (A. H. Lachlan, 1966b) Es gibt kein Paar rekursiv aufzählbarer Grade, deren Infimum ist und deren Supremum ist,
  • (L. A. Harrington and T. A. Slaman, siehe Nies, Shore, and Slaman (1998)) Die Theorie der rekursiv aufzählbaren Grade in der Sprache in Logik erster Stufe ist many-one-äquivalent zur Theorie der Arithmetik in Logik erster Stufe.

Literatur Bearbeiten

Einführungen Bearbeiten

  • S. B. Cooper: Computability Theory. Chapman & Hall/CRC, 2004, ISBN 1-58488-237-9.
  • Nigel Cutland: Computability, An introduction to recursive function theory. Cambridge University Press, 1980, ISBN 0-521-29465-7.
  • Klaus Heidler, Hans Hermes, Friedrich-K. Mahn.: Rekursive Funktionen. Mannheim – Wien – Zürich 1977.
  • Hans Hermes: Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen. Berlin/ Göttingen/ Heidelberg 1961. (2. Auflage. 1971, als Heidelberger Taschenbuch).
  • Stephen Kleene: Introduction to Metamathematics. North-Holland, 1952, ISBN 0-7204-2103-9.
  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing, 1997, ISBN 0-534-94728-X. Part Two: Computability Theory, Chapters 3–6, S. 123–222.

Spezialwerke Bearbeiten

  • Piergiorgio Odifreddi: Classical Recursion Theory. North-Holland 1989, ISBN 0-444-87295-7.
  • P. Odifreddi: Classical Recursion Theory, Volume II. Elsevier, 1999, ISBN 0-444-50205-X.
  • Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.
  • G. Sacks: Higher Recursion Theory. Springer-Verlag, 1990, ISBN 3-540-19305-7.
  • R. I. Soare: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag, 1987, ISBN 0-387-15299-7.

Forschungspapiere Bearbeiten

  • Stephen Cole Kleene, Emil L. Post: The upper semi-lattice of degrees of recursive unsolvability. In: Annals of Mathematics. Second Series. Band 59, Nr. 3, 1954, ISSN 0003-486X, S. 379–407, doi:10.2307/1969708, JSTOR:1969708.
  • A.H. Lachlan: Lower Bounds for Pairs of Recursively Enumerable Degrees. In: Proceedings of the London Mathematical Society. Band 3, Nr. 1, 1966, S. 537.
  • A.H. Lachlan: The impossibility of finding relative complements for recursively enumerable degrees. In: J. Symb. Logic. Band 31, Nr. 3, 1966, S. 434–454, doi:10.2307/2270459, JSTOR:2270459.
  • A.H. Lachlan, R.I. Soare: Not every finite lattice is embeddable in the recursively enumerable degrees. In: Advances in Math. Band 37, 1980, S. 78–82, doi:10.1016/0001-8708(80)90027-4.
  • André Nies, Richard A. Shore, Theodore A. Slaman: Interpretability and definability in the recursively enumerable degrees. In: Proc. London Math. Soc. (3). Band 77, Nr. 2, 1998, ISSN 0024-6115, S. 241–291, doi:10.1112/S002461159800046X.
  • Emil L. Post: Recursively enumerable sets of positive integers and their decision problems. In: Bulletin of the American Mathematical Society. Band 50, Nr. 5, 1944, ISSN 0002-9904, S. 284–316, doi:10.1090/S0002-9904-1944-08111-1.
  • Gerald Sacks: The recursively enumerable degrees are dense. In: Ann. Of Math.(2). Band 80, Nr. 2, 1964, S. 300–312, doi:10.2307/1970393, JSTOR:1970393.
  • Richard A. Shore, Theodore A. Slaman: Defining the Turing jump. In: Mathematical Research Letters. Band 6, 1999, ISSN 1073-2780, S. 711–722.
  • Stephen G. Simpson: First-order theory of the degrees of recursive unsolvability. In: Annals of Mathematics. Second Series. Band 105, Nr. 1, 1977, ISSN 0003-486X, S. 121–139, doi:10.2307/1971028, JSTOR:1971028.
  • Thomason, S.K.: Sublattices of the recursively enumerable degrees. In: Z. Math. Logik Grundlagen Math. Band 17, 1971, S. 273–280, doi:10.1002/malq.19710170131.
  • C.E.M. Yates: A minimal pair of recursively enumerable degrees. In: J. Symbolic Logic. Band 31, Nr. 2, 1966, S. 159–168, doi:10.2307/2269807, JSTOR:2269807.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Berechenbarkeitstheorie und der mathematischen Logik misst der Turinggrad auch Grad der Unlosbarkeit einer Menge naturlicher Zahlen die algorithmische Unlosbarkeit der Menge Das Konzept des Turinggrades ist fundamental in der Berechenbarkeitstheorie wo Mengen naturlicher Zahlen oft als Entscheidungsprobleme angesehen werden der Turinggrad einer Menge gibt an wie schwer das Entscheidungsproblem fur die Menge ist Zwei Mengen sind Turing aquivalent wenn sie den gleichen Grad der Unlosbarkeit haben jeder Turinggrad ist eine Menge Turing aquivalenter Mengen sodass zwei Mengen genau dann in unterschiedlichen Turinggraden liegen wenn sie nicht Turing aquivalent sind Ausserdem sind die Turinggrade im folgenden Sinne partiell geordnet Wenn der Turinggrad einer Menge X displaystyle X kleiner als der Turinggrad einer Menge Y displaystyle Y ist dann kann jede unberechenbare Prozedur die korrekt entscheidet ob Zahlen in Y displaystyle Y liegen berechenbar in eine Prozedur umgewandelt werden die korrekt entscheidet ob Zahlen in X displaystyle X liegen In diesem Sinne korrespondiert der Turinggrad einer Menge mit dem Grad ihrer algorithmischen Unlosbarkeit Die Turinggrade wurden 1944 von Emil Leon Post eingefuhrt und viele grundlegende Resultate wurden 1954 von Stephen Cole Kleene und Post bewiesen Die Turinggrade sind bis heute Gegenstand intensiver Forschung Viele Beweise in diesem Gebiet benutzen eine Beweistechnik die als Prioritatsmethode bekannt ist Inhaltsverzeichnis 1 Turing Aquivalenz 2 Turinggrad 3 Grundlegende Eigenschaften der Turinggrade 4 Struktur der Turinggrade 4 1 Ordnungseigenschaften 4 2 Eigenschaften des Sprungoperators 4 3 Logische Eigenschaften 5 Struktur der rekursiv aufzahlbaren Turinggrade 6 Literatur 6 1 Einfuhrungen 6 2 Spezialwerke 6 3 ForschungspapiereTuring Aquivalenz BearbeitenIm Folgenden bezieht sich das Wort Menge auf Teilmengen naturlicher Zahlen Eine Menge X displaystyle X nbsp heisst Turing reduzierbar auf eine Menge Y displaystyle Y nbsp wenn es eine Orakel Turingmaschine gibt die mit Hilfe eines Orakels fur Y displaystyle Y nbsp entscheidet ob eine gegebene Zahl in X displaystyle X nbsp liegt Die Notation X T Y displaystyle X leq T Y nbsp steht fur X displaystyle X nbsp ist auf Y displaystyle Y nbsp Turing reduzierbar Zwei Mengen X displaystyle X nbsp und Y displaystyle Y nbsp heissen Turing aquivalent wenn sie aufeinander Turing reduzierbar sind Die Notation X T Y displaystyle X equiv T Y nbsp steht fur X displaystyle X nbsp und Y displaystyle Y nbsp sind Turing aquivalent Die Relation T displaystyle equiv T nbsp ist eine Aquivalenzrelation Turinggrad BearbeitenEin Turinggrad ist eine Aquivalenzklasse der Relation T displaystyle equiv T nbsp Die Notation X displaystyle X nbsp bezeichnet die Aquivalenzklasse die die Menge X displaystyle X nbsp enthalt Die Klasse aller Turinggrade wird mit D displaystyle mathcal D nbsp bezeichnet Die Turinggrade haben eine partielle Ordnung displaystyle leq nbsp Sie ist so definiert dass X Y displaystyle X leq Y nbsp genau dann gilt wenn X T Y displaystyle X leq T Y nbsp Es gibt einen Turinggrad der genau die entscheidbaren Mengen enthalt und dieser Grad ist kleiner als alle anderen Er wird mit 0 displaystyle mathbf 0 nbsp Null bezeichnet da er das kleinste Element der partiell geordneten Menge D displaystyle mathcal D nbsp ist Turinggrade werden meist durch Fettdruck bezeichnet um sie von Mengen zu unterscheiden Als Variablen fur Turinggrade dienen fette kleine Buchstaben a b displaystyle mathbf a mathbf b nbsp etc Fur alle Mengen X displaystyle X nbsp und Y displaystyle Y nbsp ist X Y displaystyle X oplus Y nbsp gesprochen join die Vereinigung der Mengen 2 n n X displaystyle left 2n mid n in X right nbsp und 2 n 1 n Y displaystyle left 2n 1 mid n in Y right nbsp Der Turinggrad von X Y displaystyle X oplus Y nbsp ist das Supremum der Grade X displaystyle X nbsp und Y displaystyle Y nbsp Damit ist D displaystyle mathcal D nbsp ein oberer Halbverband Das Supremum der Grade a displaystyle mathbf a nbsp und b displaystyle mathbf b nbsp wird mit a b displaystyle mathbf a cup mathbf b nbsp bezeichnet Es ist bekannt dass D displaystyle mathcal D nbsp kein Verband ist da es Paare von Graden ohne Infimum gibt Fur jede Menge X displaystyle X nbsp bezeichnet X displaystyle X prime nbsp die Menge der Indizes von Orakelmaschinen die auf ihrem eigenen Index als Eingabe halten wenn sie X displaystyle X nbsp als Orakel benutzen Die Menge X displaystyle X prime nbsp wird als Turing Sprung von X displaystyle X nbsp bezeichnet Der Turing Sprung eines Grades X displaystyle X nbsp ist der Grad X displaystyle left X prime right nbsp dies ist wohldefiniert da X T Y displaystyle X prime equiv T Y prime nbsp aus X T Y displaystyle X equiv T Y nbsp folgt Ein wichtiges Beispiel ist 0 displaystyle mathbf 0 prime nbsp der Grad des Halteproblems Grundlegende Eigenschaften der Turinggrade BearbeitenJeder Turinggrad ist abzahlbar unendlich das heisst er enthalt genau ℵ 0 displaystyle aleph 0 nbsp Mengen Es gibt ℶ 1 displaystyle beth 1 nbsp siehe Beth Funktion verschiedene Turinggrade Fur jeden Grad a displaystyle mathbf a nbsp gilt die strikte Ungleichung a lt a displaystyle mathbf a lt mathbf a prime nbsp Fur jeden Grad a displaystyle mathbf a nbsp ist die Menge der Grade unter a displaystyle mathbf a nbsp hochstens abzahlbar Die Menge der Grade uber a displaystyle mathbf a nbsp hat Machtigkeit ℶ 1 displaystyle beth 1 nbsp Struktur der Turinggrade BearbeitenDie Struktur der Turinggrade wurde intensiv erforscht Die folgende Liste gibt nur wenige der vielen bekannten Ergebnisse an Generell lasst sich aus den bekannten Ergebnissen schliessen dass die Struktur der Turinggrade sehr kompliziert ist Ordnungseigenschaften Bearbeiten Es gibt minimale Grade Ein Grad a displaystyle mathbf a nbsp heisst minimal wenn a displaystyle mathbf a nbsp ungleich 0 displaystyle mathbf 0 nbsp ist und es keinen Grad zwischen 0 displaystyle mathbf 0 nbsp und a displaystyle mathbf a nbsp gibt Damit ist die Ordnung der Grade nicht dicht Fur jeden Grad a displaystyle mathbf a nbsp ungleich 0 displaystyle mathbf 0 nbsp gibt es einen Grad b displaystyle mathbf b nbsp der mit a displaystyle mathbf a nbsp nicht vergleichbar ist Es gibt ℶ 1 displaystyle beth 1 nbsp untereinander nicht vergleichbare Turinggrade Es gibt Paare von Graden ohne Infimum Damit ist D displaystyle mathcal D nbsp kein Verband Jede abzahlbare partielle Ordnung lasst sich in die Turinggrade einbetten Keine unendliche strikt aufsteigende Folge von Graden hat ein Supremum Eigenschaften des Sprungoperators Bearbeiten Fur jeden Grad a displaystyle mathbf a nbsp gibt es einen Grad zwischen a displaystyle mathbf a nbsp und a displaystyle mathbf a prime nbsp Es gibt sogar eine abzahlbar unendliche Folge paarweise nicht vergleichbarer Grade zwischen a displaystyle mathbf a nbsp und a displaystyle mathbf a prime nbsp Ein Grad a displaystyle mathbf a nbsp hat die Form b displaystyle mathbf b prime nbsp fur ein b displaystyle mathbf b nbsp genau dann wenn 0 lt a displaystyle mathbf 0 lt mathbf a nbsp gilt Fur jeden Grad a displaystyle mathbf a nbsp gibt es einen Grad b displaystyle mathbf b nbsp sodass a lt b displaystyle mathbf a lt mathbf b nbsp und a b displaystyle mathbf a prime mathbf b prime nbsp Solch ein Grad b displaystyle mathbf b nbsp heisst niedrig relativ zu a displaystyle mathbf a nbsp Es gibt eine unendliche Folge a i i displaystyle left mathbf a i right i nbsp von Graden sodass a i 1 a i displaystyle mathbf a i 1 prime leq mathbf a i nbsp fur alle i displaystyle i nbsp Logische Eigenschaften Bearbeiten Simpson 1977 zeigte dass die Theorie von D displaystyle mathcal D nbsp in der Pradikatenlogik erster Stufe in der Sprache displaystyle left langle leq right rangle nbsp oder displaystyle left langle leq cdot prime right rangle nbsp many one aquivalent zur Theorie der naturlichen Zahlen in der Pradikatenlogik zweiter Stufe ist Shore und Slaman 1999 zeigten dass sich der Sprungoperator in der Struktur der Grade in der Logik erster Stufe mit der Sprache displaystyle left langle leq right rangle nbsp definieren lasst Struktur der rekursiv aufzahlbaren Turinggrade Bearbeiten nbsp Dieser endliche Verband kann nicht in die rekursiv aufzahlbaren Grade eingebettet werden Ein Grad heisst rekursiv aufzahlbar wenn er eine rekursiv aufzahlbare Menge enthalt Jeder rekursiv aufzahlbare Grad ist kleiner oder gleich 0 displaystyle mathbf 0 prime nbsp aber nicht jeder Grad kleiner 0 displaystyle mathbf 0 prime nbsp ist rekursiv aufzahlbar Satz von Friedberg und Muchnik 1956 Es gibt rekursiv aufzahlbare Grade zwischen 0 displaystyle mathbf 0 nbsp und 0 displaystyle mathbf 0 prime nbsp G E Sacks 1964 Die rekursiv aufzahlbaren Grade sind dicht das heisst zwischen zwei rekursiv aufzahlbaren Graden existiert immer ein dritter rekursiv aufzahlbarer Grad A H Lachlan 1966a and C E M Yates 1966 Es gibt zwei rekursiv aufzahlbare Grade die kein Infimum in den rekursiv aufzahlbaren Graden haben A H Lachlan 1966a and C E M Yates 1966 Es gibt ein Paar von rekursiv aufzahlbaren Graden ungleich 0 displaystyle mathbf 0 nbsp deren Infimum 0 displaystyle mathbf 0 nbsp ist S K Thomason 1971 Jeder endlicher distributiver Verband kann in die rekursiv aufzahlbaren Grade eingebettet werden Es ist sogar moglich die abzahlbare boolesche Algebra ohne Atome so einzubetten dass Suprema und Infima erhalten bleiben A H Lachlan and R I Soare 1980 Nicht alle endlichen Verbande konnen in die rekursiv aufzahlbaren Grade eingebettet werden sodass Suprema und Infima erhalten bleiben So kann insbesondere der rechts abgebildete Verband nicht eingebettet werden A H Lachlan 1966b Es gibt kein Paar rekursiv aufzahlbarer Grade deren Infimum 0 displaystyle mathbf 0 nbsp ist und deren Supremum 0 displaystyle mathbf 0 prime nbsp ist L A Harrington and T A Slaman siehe Nies Shore and Slaman 1998 Die Theorie der rekursiv aufzahlbaren Grade in der Sprache 0 displaystyle left langle mathbf 0 leq right rangle nbsp in Logik erster Stufe ist many one aquivalent zur Theorie der Arithmetik in Logik erster Stufe Literatur BearbeitenEinfuhrungen Bearbeiten S B Cooper Computability Theory Chapman amp Hall CRC 2004 ISBN 1 58488 237 9 Nigel Cutland Computability An introduction to recursive function theory Cambridge University Press 1980 ISBN 0 521 29465 7 Klaus Heidler Hans Hermes Friedrich K Mahn Rekursive Funktionen Mannheim Wien Zurich 1977 Hans Hermes Aufzahlbarkeit Entscheidbarkeit Berechenbarkeit Einfuhrung in die Theorie der rekursiven Funktionen Berlin Gottingen Heidelberg 1961 2 Auflage 1971 als Heidelberger Taschenbuch Stephen Kleene Introduction to Metamathematics North Holland 1952 ISBN 0 7204 2103 9 Michael Sipser Introduction to the Theory of Computation PWS Publishing 1997 ISBN 0 534 94728 X Part Two Computability Theory Chapters 3 6 S 123 222 Spezialwerke Bearbeiten Piergiorgio Odifreddi Classical Recursion Theory North Holland 1989 ISBN 0 444 87295 7 P Odifreddi Classical Recursion Theory Volume II Elsevier 1999 ISBN 0 444 50205 X Hartley Rogers Theory of recursive functions and effective computability McGraw Hill 1967 G Sacks Higher Recursion Theory Springer Verlag 1990 ISBN 3 540 19305 7 R I Soare Recursively Enumerable Sets and Degrees Perspectives in Mathematical Logic Springer Verlag 1987 ISBN 0 387 15299 7 Forschungspapiere Bearbeiten Stephen Cole Kleene Emil L Post The upper semi lattice of degrees of recursive unsolvability In Annals of Mathematics Second Series Band 59 Nr 3 1954 ISSN 0003 486X S 379 407 doi 10 2307 1969708 JSTOR 1969708 A H Lachlan Lower Bounds for Pairs of Recursively Enumerable Degrees In Proceedings of the London Mathematical Society Band 3 Nr 1 1966 S 537 A H Lachlan The impossibility of finding relative complements for recursively enumerable degrees In J Symb Logic Band 31 Nr 3 1966 S 434 454 doi 10 2307 2270459 JSTOR 2270459 A H Lachlan R I Soare Not every finite lattice is embeddable in the recursively enumerable degrees In Advances in Math Band 37 1980 S 78 82 doi 10 1016 0001 8708 80 90027 4 Andre Nies Richard A Shore Theodore A Slaman Interpretability and definability in the recursively enumerable degrees In Proc London Math Soc 3 Band 77 Nr 2 1998 ISSN 0024 6115 S 241 291 doi 10 1112 S002461159800046X Emil L Post Recursively enumerable sets of positive integers and their decision problems In Bulletin of the American Mathematical Society Band 50 Nr 5 1944 ISSN 0002 9904 S 284 316 doi 10 1090 S0002 9904 1944 08111 1 Gerald Sacks The recursively enumerable degrees are dense In Ann Of Math 2 Band 80 Nr 2 1964 S 300 312 doi 10 2307 1970393 JSTOR 1970393 Richard A Shore Theodore A Slaman Defining the Turing jump In Mathematical Research Letters Band 6 1999 ISSN 1073 2780 S 711 722 Stephen G Simpson First order theory of the degrees of recursive unsolvability In Annals of Mathematics Second Series Band 105 Nr 1 1977 ISSN 0003 486X S 121 139 doi 10 2307 1971028 JSTOR 1971028 Thomason S K Sublattices of the recursively enumerable degrees In Z Math Logik Grundlagen Math Band 17 1971 S 273 280 doi 10 1002 malq 19710170131 C E M Yates A minimal pair of recursively enumerable degrees In J Symbolic Logic Band 31 Nr 2 1966 S 159 168 doi 10 2307 2269807 JSTOR 2269807 Abgerufen von https de wikipedia org w index php title Turinggrad amp oldid 202534602