Terminiert (oder terminierend) heißt ein Algorithmus dann, wenn er für jede Eingabe nach endlich vielen Schritten anhält, das heißt dass die Berechnung in endlicher Zeit abgeschlossen wird. Diese Eigenschaft ist eng verbunden mit der Entscheidbarkeit: für jedes entscheidbare Problem gibt es Algorithmen, die stets terminieren, für nicht-entscheidbare Probleme gibt es keinen Algorithmus, der stets terminiert. Aussagen über die Terminiertheit von Algorithmen sind ein Grundstein der Berechenbarkeitstheorie, welche ein Teilgebiet der theoretischen Informatik darstellt.

Eine wichtige Aufgabe der Verifikation (dem Beweis der Korrektheit eines Programms) ist es, zu zeigen, dass das vorliegende Programm für jede mögliche Eingabe anhält. Das ist jedoch im allgemeinen nicht möglich: es gibt keine Methode, für einen beliebigen Algorithmus (z.B. in Form eines Computerprogramms) zu zeigen, dass er nach endlich vielen Schritten terminiert - das folgt aus der Unlösbarkeit des Halteproblems.

Beweis der Terminiertheit

---

Für ausgewählte Algorithmen ist es mit dem Methoden der formalen Semantik möglich, zu bestimmen, für welche Eingaben sie halten und für welche nicht. Eine Möglichkeit besteht darin, mit Hilfe einer Abstiegsfunktion die Terminiertheit induktiv zu beweisen.

Beispiel: Terminiertheit der Ackermannfunktion

In der Praxis ist die Berechnung Ackermannfunktion A(k,n) nur für kleine k und n möglich. Trotzdem kann man zeigen, dass der folgende Algorithmus für alle k und n terminiert.

A(0,n)=n+1

A(m+1,0)=A(m,1)

A(m+1,n+1)=A(m,A(m+1,n))

Siehe auch: Determinismus (Algorithmus), Determiniertheit (Algorithmus), Terminierung

Theoretische Informatik