Church-Turing-These
Bewertung von Berechnungsmodellen
Wir haben in den Abschnitten Turingmaschine als Berechnungsmodell, Registermaschine als Berechnungsmodell und While-Programmiersprache als Berechnungsmodell verschiedene Berechnungsmodelle zur Präzisierung der Idee "Computer" / "algorithmisch automatisierbar" eingeführt. Es ergeben sich eine Reihe von grundsätzlichen Fragen:
Inwieweit unterscheiden sich die verschiedenen Berechnungsmodelle überhaupt? Welche sind mächtiger / weniger mächtig in dem Sinne, dass mehr / weniger Probleme mit den zur Verfügung gestellten Mitteln gelöst werden können?
Welches Berechnungsmodell erfasst am ehesten die Idee "algorithmisch automatisierbar"? Handelt es sich um adäquate Berechnungsmodelle in dem Sinn, dass die Idee "algorithmisch automatisierbar" auch "richtig" modelliert wird?
Wir gehen diesen Fragen in den folgenden Abschnitten nach.
Äquivalenz von Berechnungsmodellen
Der Umgang mit den verschiedenen Berechnungsmodellen lässt bereits erahnen, dass sie in folgendem Sinn gleichwertig sind:
Satz (über die Äquivalenz von Berechnungsmodellen)
Eine (k-stellige) Funktion f ist Turingmaschinen-berechenbar genau dann, wenn sie Registermaschinen-berechenbar ist bzw. genau dann, wenn sie While-berechenbar ist.
Hinsichtlich ihrer Mächtigkeit unterscheiden sich die Berechnungsmodelle also nicht.
Der Nachweis dieser Äquivalenzaussage ist recht aufwendig. Wir verzichten daher hier auf den Nachweis.
Es gibt eine ganze Reihe weiterer Präzisierungsansätze, die zu noch mehr Berechnungsmodellen führen. Besonders interessant sind hier die Ansätze, die alternative Programmierkonzepte oder auch alternative Rechnerarchitekturen aufgreifen. Wir werden diese Ansätze hier nicht weiter verfolgen. Es zeigt sich, dass alle Präzisierungen der Idee "algorithmisch automatisierbar" äquivalent sind und zur gleichen Klasse berechenbarer Funktionen führen.
Adäquatheit von Berechnungsmodellen
Die Tatsache, dass alle Versuche, den Berechenbarkeitsbegriff mathematisch zu präzisieren, zur gleichen Klasse berechenbarer Funktionen geführt hat, sehen viele als Bestätigung dafür, dass der intuitive Berechenbarkeitsbegriff durch die bisher entwickelten Berechnungsmodelle adäquat erfasst wird. Diese These wurde erstmals von Alonzo Church und Alan Turing - den Entwicklern der ersten Berechnungsmodelle - formuliert.
Church-Turing-These
Eine Funktion ist im intuitiven Sinn berechenbar genau dann, wenn sie Turingmaschinen-berechenbar ist bzw. genau dann, wenn sie Registermaschinen-berechenbar ist bzw. genau dann, wenn sie While-berechenbar ist bzw. genau dann, ...
Beachte, dass die Church-Turing-These keine mathematisch präzise Aussage ist, da hier der nicht präzisierte Begriff "im intuitiven Sinne berechenbar" vorkommt. Die Church-Turing-These drückt vielmehr die Erfahrung vieler Informatiker aus, die sich mit der Präzisierung des Algorithmusbegriffs beschäftigt haben.