Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit / Grundlehren der mathematischen Wissenschaften Bd.109 (PDF)

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össten 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 grosser 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 Schluss­ 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, dass 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 Anstoss gegeben, die Frage nach dem Wesen des Algorithmus aufzuwerfen. Diese Frage hatte schon Leibniz gestellt, aber nicht zu lösen vermocht.