Informatikmaterialien
von Tino Hempel

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

Churchsche Hypothese und Turing-Berechenbarkeit

Zur Präzisierung des Algorithmusbegriffs greifen wir die Idee der Turingmaschine wieder auf, wenden Sie aber nicht als Akzeptor an.

Turingmaschine

Bisher wurde die TM als Akzeptor eingesetzt. Sie war in der Lage Grammatiken ab Typ 0 zu erkennen. Im folgenden soll die TM als Rechenmaschine arbeiten, also aus einer Eingabe eine Ausgabe mit Hilfe einer Schrittfolge (Zustandsübergänge) ermitteln.

Beispiel: Man konstruiere eine TM, die zwei natürliche Zahlen in unärer Darstellung addiert (also III+II). Der Kopf der TM steht zu Beginn der Rechnung am Anfang der ersten Zahl.

Lösung:

Eine Funktion f: X* X* heißt turingberechenbar, wenn es eine TM gibt, so dass für alle Wörter w, v X* gilt:
f(w) = v genau dann, wenn die TM beginnend im Startzustand mit dem Eingabewort w durch definierte Zusandsübergänge in einen Endzustand gelangt und dann das Wort v auf dem Band steht.

Churchsche Hypothese

Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Die TM ist ein Algorithmus.

Die Definition der Turingberechenbarkeit beschreibt genau dass, was man von einer berechenbaren Funktion und damit von einem Algorithmus erwartet. Die Churchsche These ist nicht beweisbar, die Mehrzahl der Informatiker akzeptiert sie.

Damit stellt sich aber noch die Frage nach dem Verhältnis von definierbaren zu berechenbaren Funktionen. Mit Hilfe mathematischer Verfahren (Cantorsches Diagonalisierungsverfahren 2. Art) lässt sich beweisen, dass es leider mehr definierbare Funktionen als berechenbare Funktionen gibt. Damit ergibt sich die Konsequenz, dass es Funktionen gibt, die sich nicht mit Hilfe einer Turingmaschine und damit eines Algorithmus und damit eines Computers lösen lassen.

Ein Beispiel für eine solche Funktion bzw. Fragestellung ist das sog. Halteproblem: Gibt es einen universellen Algorithmus, der einen beliebigen Algorithmus untersucht und die Frage beantwortet, ob er bei der Eingabe beliebiger Daten in eine Endlosschleife gerät oder nicht? Einen solchen Algorithmus gibt es nicht.

zur Startseite

Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel..