Das Kefk Network Wiki befindet sich im Testbetrieb.
Terminiertheit
Aus Kefk.
Terminiertheit ist ein Begriff aus der Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik. Ein Algorithmus heißt terminierend, wenn er für jede Eingabe nach endlich vielen Arbeitsschritten anhält, so dass die Berechnung in endlicher Zeit abgeschlossen wird. Dabei wird keine für alle Eingaben gemeinsam gültige Obergrenze für die Anzahl der ausgeführten Arbeitsschritte gefordert. Beispielsweise wächst die Anzahl zur Berechnung der Ackermannfunktion notwendigen Arbeitsschritte unbeschränkt für wachsende Eingabeparameter. Gleichwohl kann man zeigen, dass der entsprechende rekursive Algorithmus
für alle Eingabewerte n und m nach einer endlichen Anzahl von Arbeitsschritten terminiert.
Die Eigenschaft der Terminiertheit eines Algorithmus 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.
Eine wichtige Aufgabe der Verifikation eines Computerprogramms (dem Beweis der Korrektheit) ist es, zu zeigen, dass das vorliegende Programm für jede mögliche Eingabe anhält. Aus der Unlösbarkeit des Halteproblems folgt, dass dieser Nachweis im allgemeinen nicht möglich ist.
Methoden zum Nachweis der Terminiertheit
Für ausgewählte Algorithmen ist es mit den 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.
Siehe auch
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Terminiertheit, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
