weiter	hoch	zurück	Inhalt	Index

Berechenbarkeit

Als Einstieg in die Theorie der Berechenbarkeit versuchen wir uns in eine Zeit zurückzuversetzen, in der es den Begriff einer berechenbaren Funktion noch nicht gab. Ja mehr noch, in der man sich nicht vorstellen konnte, daß es so etwas wie prinzipielle Unberechenbarkeit für jetzt und alle Zeiten überhaupt gibt. Für eine solche Rückblende eignet sich das zehnte HILBERTsche Problem besonders gut. In den darauf folgenden drei Abschnitten stellen wir drei formale Definitionen des Begriffs einer berechenbaren Funktionen vor. Die erste orientiert sich an dem Modell einer Maschine, das die Berechnung durchführt. In der zweiten Definition wird dieser Aspekt in den Hintergrund geschoben und statt dessen die Programmierung einer Berechnung betont. Der dritte Zugang schließlich ist strikt mathematisch. Es wird induktiv eine Klasse von Funktionen definiert, die auf den ersten Blick nichts mit der Idee der Berechbarkeit zu tun haben. Die drei Definitionen sind äquivalent, das heißt sie führen zur selben Klasse berechenbarer Funktionen. Darauf gehen wir in Abschnitt 1.5 näher ein. Nach der Einführung einer formalen Definition sind wir in der Lage Unberechenbarkeitresultate in einem strikten mathematischen Sinn zu beweisen. Das wird zunächst für die Urzelle aller Unberechenbarkeitsresultate, das Halteproblem, gezeigt und dann auf weitere Probleme ausgedehnt.

weiter	hoch	zurück	Inhalt	Index