Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Genera...

"Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets" von Robert I. Soare ist ein umfassendes Werk, das sich mit der Theorie der rekursiv aufzählbaren Mengen und den damit verbundenen Graden befasst. Das Buch bietet eine tiefgehende Untersuchung der Struktur und Eigenschaften von rekursiv aufzählbaren Mengen, die zentrale Objekte in der Berechenbarkeitstheorie sind. Soare behandelt sowohl klassische Ergebnisse als auch moderne Entwicklungen in diesem Bereich und bietet einen detaillierten Einblick in die Hierarchien und Beziehungen zwischen verschiedenen Klassen von Problemen hinsichtlich ihrer Berechenbarkeit. Ein besonderer Fokus liegt auf den sogenannten Turing-Graden, die eine Möglichkeit darstellen, die Komplexität nicht nur einzelner Probleme, sondern ganzer Klassen zu vergleichen. Das Buch richtet sich an Leser mit einem fortgeschrittenen mathematischen Hintergrund und Interesse an Logik und theoretischer Informatik. Es ist sowohl als Lehrbuch für Studierende als auch als Referenzwerk für Forscher geeignet, die sich mit der Theorie der Berechenbarkeit beschäftigen.