Terminiertheit

Terminiertheit ist ein Begriff aus der Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik. Man sagt, ein Algorithmus terminiert für die Eingabe a, wenn er für die Eingabe a nach endlich vielen Arbeitsschritten zu einem Ende kommt, so dass die Berechnung in endlicher Zeit abgeschlossen wird. Man sagt, der Algorithmus terminiert überall oder ist terminierend, wenn er für jede Eingabe terminiert. Dabei wird keine für alle Eingaben gemeinsam gültige Obergrenze für die Anzahl der ausgeführten Arbeitsschritte gefordert.

Eine wichtige Aufgabe der Verifikation eines Computerprogramms (dem Beweis der Korrektheit) ist es, zu zeigen, dass das vorliegende Programm für gewisse Eingaben terminiert. Aus der Nicht-Entscheidbarkeit des Halteproblems folgt, dass es keinen, für jedes Paar gültigen, Algorithmus gibt, der zu einem Paar (Programm, Eingabe) immer entscheiden kann, ob das Programm terminiert. Auch die Frage, ob ein Programm überall terminiert, ist unentscheidbar. Dies folgt aus einer Abwandlung des Halteproblems, dem uniformen Halteproblem.

Für viele praktische Algorithmen ist deren Terminierung aber einfach zu beweisen. Ein bekanntes Beispiel für eine Funktion, zu der bewiesen wurde, dass es für sie kein terminierendes Berechnungsverfahren gibt, ist die Radó-Funktion. Das Collatz-Problem ist ein Beispiel für eine Funktion, für die weder ein terminierendes Berechnungsverfahren gefunden wurde, noch bewiesen wurde, dass es ein solches Verfahren nicht gibt.