Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit : Einführung in die Theorie der Rekursiven Funktionen

Man nennt eine Funktion berechenbar, wenn es einen Algorithmus zur Auffindung der Werte für beliebige vorgegebene Argumente gibt. -Es wird jedoch überall dort, wo Beweise konstruktiv durchgeführt werden, diese Tatsache besonders hervorgehoben.Im Gegensatz zu manchen einschlägigen Publikationen wird Wert darauf gelegt, Formeln einer Sprache und das durch diese Bezeichnete zu unterscheiden, jedenfalls in den grundlegenden Definitionen.Am Ende von verschiedenen Paragraphen finden sich einige meist leichte übungsaufgaben, die den Leser zu selbständiger Mitarbeit anregen sollen.Dem einführenden Charakter dieses Buches entspricht es, daß nicht alle einschlägigen Untersuchungen besprochen werden können. Die Literaturangaben am Schlusse der meisten Paragraphen führen jedoch den Leser an den neuesten Stand der Theorie heran. Außerdem sei der Leser hier ein für allemal verwiesen auf das grundlegende Werk von S. C. In der Mathematik ist es immer als eine besonders interessante und wichtige Aufgabe angesehen worden, Algorithmen zur Lösung von Pro­ blemen zu entwickeln. Dabei ist ein Algorithmus im Normalfall nur auf einen eng umschriebenen Problemkreis anwendbar, wie etwa der Euklidi­ sche Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen oder das bekannte Verfahren, mit dessen Hilfe die Qua­ dratwurzeln aus natürlichen Zahlen in Dezimaldarstellung gewonnen werden können. So wichtig derartige spezielle Algorithmen auch sein mögen - so wäre es dennoch wünschenswert, über Algorithmen mit großer Tragweite zu verfügen. Um solche Algorithmen, die sich mög­ lichst vielfältig anwenden lassen, hat man sich jahrhundertelang ohne rechten Erfolg bemüht. Erst in der zweiten Hälfte des letzten Jahr­ hunderts wurde ein bemerkenswerter Fortschritt erzielt, als es gelang, mit der Prädikatenlogik einen wichtigen Teil der logischen Schluß­ prozesse in die Gestalt eines Kalküls zu bringen. (Dabei spielte die Boolesche Algebra eine wesentliche Pionierrolle.) Man hätte nun viel­ leicht vermuten können, daß alle mathematischen Probleme algorith­ misch lösbar seien. Doch mahnten wohlbekannte noch ungelöste Pro­ bleme (etwa das Wortproblem der Gruppentheorie, oder das zehnte Hilbertsche Problem, das die Frage nach der Lösbarkeit von diophanti­ schen Gleichungen betrifft) zur Vorsicht. Immerhin war nun der Anstoß gegeben, die Frage nach dem Wesen des Algorithmus aufzuwerfen. Diese Frage hatte schon Leibniz gestellt, aber nicht zu lösen vermocht. Front Matter....Pages II-X Einführende Betrachtungen über Algorithmen....Pages 1-32 Turingmaschinen....Pages 33-59 μ-Rekursive Funktionen....Pages 59-95 Die Äquivalenz von Turing-Berechenbarkeit und μ-Rekursivität....Pages 95-114 Rekursive Funktionen....Pages 114-142 Unentscheidbare Prädikate....Pages 142-187 Verschiedenes....Pages 188-240 Erratum to: μ-Rekursive Funktionen....Pages 247-247 Erratum to: Die Äquivalenz von Turing-Berechenbarkeit und μ-Rekursivität....Pages 247-247 Erratum to: Rekursive Funktionen....Pages 247-247 Erratum to: Unentscheidbare Prädikate....Pages 247-247 Back Matter....Pages 241-246