Computability. Recursive and programmable functions (Q1308644)

Es wird die Theorie der Berechenbarkeit in einer im wesentlichen maschinenunabhängigen Form präsentiert. Der Schwerpunkt liegt in diesem Buch vielmehr auf Berechnungsvorschriften, die durch entsprechende Rekursionsschemata für arithmetische Funktionen gegeben sind, oder solche Berechnungsvorschriften, die durch entsprechende Programme oder durch Kalküle gegeben sind. Hierbei werden sowohl Termersetzungs- als auch Gleichungskalküle behandelt. Ein gewisser Schwerpunkt liegt ferner auf den subrekursiven Funktionsklassen, wie die elementaren Funktionen, die primitiv-rekursiven Funktionen, die simplen Funktionen und die Klassen der Grzegorczyk- und der Schleifen-Hierarchie. Die Darstellung ist äußerst präzise, man wird an keiner Stelle ein ``hard waving'' Beweisargument finden. Andererseits wir die Lesbarkeit des Buches durch (meines Erachtens unnötig) viele Notationen und Abkürzungen erschwert. Will man in ein Kapitel ``quereinsteigen'', so wird dieser Versuch sofort durch die Notwendigkeit, eine Unmenge von Notationen nachschlagen zu müssen, bestraft. Der disziplinierte Leser, der das Buch von vorne nach hinten liest, wird dagegen für seine Mühen belohnt: dies vor allem deshalb, weil die Berechenbarkeitstheorie eine intellektuelle Ästhetik besitzt (die ihr letztlich keine Form der Darstellung nehmen kann).