Übersichtsartikel zur Theorie rekursiver Funktionen?

8

Könnten Sie einen Umfrageartikel oder ein Lehrbuchkapitel empfehlen, in dem die Theorie der rekursiven Funktionen vorgestellt wird? Vielen Dank

reference-request computability Schüchterne Person
quelle

Antworten:

9

Eine schöne Referenz ist "Teil C" des Handbuchs der mathematischen Logik, herausgegeben von Barwise. Teil C enthält die folgenden Kapitel:

  • Herbert B. Enderton , Elemente der Rekursionstheorie
  • Martin Davis , unlösbare Probleme
  • Michael O. Rabin , Entscheidbare Theorien
  • Stephen G. Simpson , Grad der Unlösbarkeit: eine Übersicht der Ergebnisse
  • Richard A. Shore , Rekursionstheorieα
  • Alexander Kechris und Yiannis N. Moschovakis , Rekursion in höheren Typen
  • Peter Aczel , Eine Einführung in induktive Definitionen
  • Donald A. Martin , Beschreibende Mengenlehre

Die Kapitel sind von sehr hoher Qualität und werden von führenden Logikern geschrieben. Dieses Handbuch führt Sie ziemlich weit in die Welt der mathematischen Logik.

Dai Le
quelle
9

Die meisten Bücher zur Logik- / Komplexitätstheorie enthalten ein Kapitel zur Berechenbarkeit.

Lehrbuch:

Dexter Kozen, " Theory of Computation ", Springer, 2006

Douglas S. Bridges, " Computability: a Mathematical Sketchbook ", Springer, 1994

Nigel Cutland, " Berechenbarkeit, eine Einführung in die rekursive Funktionstheorie ", Cambridge University Press, 1980

Barry S. Cooper, " Computability Theory ", Chapman & Hall / CRC, 2004

Weiterführendes Buch:

Robert I. Soare, " Rekursiv aufzählbare Mengen und Grade ", Springer-Verlag, 1987

Robert I. Soare, "Berechenbarkeitstheorie und -anwendungen: Die Kunst der klassischen Berechenbarkeit"

Piergiorgio Odifreddi, " Classical Recursion Theory ", Band I (1989) & II (1999)

Edward R. Griffor, " Handbuch der Berechenbarkeitstheorie ", Elsevier, 1999

Kaveh
quelle
In der Liste der Lehrbücher hat das erste "Computably Enumerable Sets and Degrees" eine andere Titelform als das, was Sie verknüpft haben ("Recursively Enumerable Sets and Degrees").
MS Dousti
@Sadeq Dousti: Sie haben Recht, ich glaube, ich habe den Titel von der Webseite des Autors kopiert.
Kaveh
Also habe ich es bearbeitet, um den veröffentlichten Titel wiederzugeben. PS: Das Buch "Theorie und Anwendungen der Berechenbarkeit: Die Kunst der klassischen Berechenbarkeit" muss noch veröffentlicht werden, oder?
MS Dousti
@Sadeq: Ich denke, er zieht es vor, das Wort rekursiv für berechenbar in letzter Zeit zu vermeiden. ps: Ich denke schon, aber Sie können ihn wahrscheinlich bitten, die Entwurfsversion zu bekommen. Wir haben sie vor einigen Jahren in einem Kurs verwendet.
Kaveh
6

Ich mag den Lehrplan, den Sebastiaan Terwijn 2004 geschrieben hat (zugänglich unter http://www.math.ru.nl/~terwijn/teaching.html ). Es behandelt rekursive Funktionen und Mengen, Rückstellungen, die arithmetische Hierarchie, Turing-Grade, die Prioritätsmethode und einige Anwendungen, einschließlich Unvollständigkeitssätzen.

Michaël Cadilhac
quelle
5

Ich fand diese Bücher zu meiner Verfügung. Ich habe überprüft, ob die von Kaveh zitierten Bücher nicht enthalten sind , aber meine Augen haben möglicherweise einen Fehler gemacht.

MS Dousti
quelle
@ Kaveh: Danke. Es scheint, dass ich eine Brille brauche :)
MS Dousti