Terminierungsanalyse – Wikipedia

void f(int n) {
   while (n > 1)
      if (n % 2 == 0)
          n = n / 2;
      else
          n = 3 * n + 1;
}

In der Informatik Terminierungsanalyse ist eine Programmanalyse, die versucht festzustellen, ob die Auswertung eines bestimmten Programms für anhält jeder Eingang. Dies bedeutet zu bestimmen, ob das Eingabeprogramm a berechnet gesamt Funktion.

Es hängt eng mit dem Halteproblem zusammen, bei dem festgestellt wird, ob ein bestimmtes Programm für a angehalten wird gegeben Eingabe und die ist unentscheidbar. Die Terminierungsanalyse ist noch schwieriger als das Halteproblem: Die Terminierungsanalyse im Modell von Turing-Maschinen als Modell von Programmen, die berechenbare Funktionen implementieren, hätte das Ziel zu entscheiden, ob eine bestimmte Turing-Maschine eine gesamte Turing-Maschine ist, und dieses Problem ist es auf Ebene

der arithmetischen Hierarchie und ist daher streng schwieriger als das Halting-Problem.

Da nun die Frage, ob eine berechenbare Funktion total ist, nicht halb entscheidbar ist,^[1] jeder Klang Terminierungsanalysator (dh eine positive Antwort wird für ein nicht terminierendes Programm niemals gegeben) ist unvollständigDas heißt, es muss fehlschlagen, die Beendigung für unendlich viele Beendigungsprogramme zu bestimmen, entweder durch ewiges Ausführen oder durch Anhalten mit einer unbestimmten Antwort.

Kündigungsnachweis[edit]

EIN Kündigungsnachweis ist eine Art mathematischer Beweis, der eine entscheidende Rolle bei der formalen Verifizierung spielt, da die vollständige Korrektheit eines Algorithmus von der Beendigung abhängt.

Eine einfache, allgemeine Methode zum Erstellen von Kündigungsnachweisen besteht darin, a zuzuordnen messen mit jedem Schritt eines Algorithmus. Das Maß wird aus dem Bereich einer begründeten Beziehung entnommen, beispielsweise aus den Ordnungszahlen. Wenn das Maß gemäß der Beziehung in jedem möglichen Schritt des Algorithmus “abnimmt”, muss es beendet werden, da es in Bezug auf eine fundierte Beziehung keine unendlichen absteigenden Ketten gibt.

Einige Arten der Terminierungsanalyse können automatisch das Vorhandensein eines Terminierungsnachweises generieren oder implizieren.

Beispiel[edit]

Ein Beispiel für ein Programmiersprachenkonstrukt, das möglicherweise beendet wird oder nicht, ist eine Schleife, da sie wiederholt ausgeführt werden können. Schleifen, die unter Verwendung einer Zählervariablen implementiert werden, wie sie normalerweise in Datenverarbeitungsalgorithmen zu finden sind, werden normalerweise beendet, wie das folgende Pseudocode-Beispiel zeigt:

i := 0
loop until i = SIZE_OF_DATA
    process_data(data[i])) // process the data chunk at position i
    i := i + 1 // move to the next chunk of data to be processed

Wenn der Wert von SIZE_OF_DATA ist nicht negativ, fest und endlich, wird die Schleife schließlich enden, vorausgesetzt Prozessdaten endet auch.

Es kann gezeigt werden, dass einige Schleifen immer oder niemals durch menschliche Inspektion enden. Zum Beispiel wird die folgende Schleife theoretisch niemals aufhören. Es kann jedoch aufgrund eines arithmetischen Überlaufs angehalten werden, wenn es auf einer physischen Maschine ausgeführt wird: Dies führt entweder zu einer Ausnahme oder dazu, dass der Zähler auf einen negativen Wert umbrochen wird und die Schleifenbedingung erfüllt werden kann.

i := 1
loop until i = 0
    i := i + 1

Bei der Beendigungsanalyse kann man auch versuchen, das Beendigungsverhalten eines Programms in Abhängigkeit von einer unbekannten Eingabe zu bestimmen. Das folgende Beispiel veranschaulicht dieses Problem.

i := 1
loop until i = UNKNOWN
    i := i + 1

Hier wird die Schleifenbedingung unter Verwendung eines Wertes UNKNOWN definiert, wobei der Wert von UNKNOWN nicht bekannt ist (z. B. definiert durch die Benutzereingabe, wenn das Programm ausgeführt wird). Hier muss die Beendigungsanalyse alle möglichen Werte von UNBEKANNT berücksichtigen und herausfinden, dass im möglichen Fall von UNBEKANNT = 0 (wie im ursprünglichen Beispiel) die Beendigung nicht angezeigt werden kann.

Es gibt jedoch kein allgemeines Verfahren zum Bestimmen, ob ein Ausdruck mit Schleifenanweisungen angehalten wird, selbst wenn Menschen mit der Inspektion beauftragt sind. Der theoretische Grund dafür ist die Unentscheidbarkeit des Halteproblems: Es kann keinen Algorithmus geben, der bestimmt, ob ein bestimmtes Programm nach endlich vielen Berechnungsschritten stoppt.

In der Praxis wird keine Beendigung (oder Nichtbeendigung) angezeigt, da jeder Algorithmus mit einem endlichen Satz von Methoden arbeitet, die in der Lage sind, relevante Informationen aus einem bestimmten Programm zu extrahieren. Eine Methode könnte untersuchen, wie sich Variablen in Bezug auf eine Schleifenbedingung ändern (möglicherweise wird die Beendigung für diese Schleife angezeigt), andere Methoden könnten versuchen, die Berechnung des Programms in ein mathematisches Konstrukt umzuwandeln und daran zu arbeiten, um möglicherweise Informationen über das Beendigungsverhalten zu erhalten Einige Eigenschaften dieses mathematischen Modells. Da jedoch jede Methode nur bestimmte Gründe für eine (Nicht-) Beendigung “sehen” kann, kann man selbst durch die Kombination solcher Methoden nicht alle möglichen Gründe für eine (Nicht-) Beendigung abdecken.^{[citation needed]}

Rekursive Funktionen und Schleifen sind im Ausdruck äquivalent. Jeder Ausdruck mit Schleifen kann durch Rekursion geschrieben werden und umgekehrt. Daher ist die Beendigung rekursiver Ausdrücke auch im Allgemeinen unentscheidbar. Es kann gezeigt werden, dass die meisten im allgemeinen Sprachgebrauch vorkommenden rekursiven Ausdrücke (dh nicht pathologisch) auf verschiedene Weise enden, normalerweise abhängig von der Definition des Ausdrucks selbst. Beispielsweise wird das Funktionsargument im rekursiven Ausdruck für die folgende Fakultätsfunktion immer um 1 verringert. Durch die gut geordnete Eigenschaft natürlicher Zahlen wird das Argument schließlich 1 erreichen und die Rekursion wird beendet.

function factorial (argument as natural number)
    if argument = 0 or argument = 1
        return 1
    otherwise
        return argument * factorial(argument - 1)

Abhängige Typen[edit]

Die Terminierungsprüfung ist in abhängig typisierten Programmiersprachen und Theoremprüfsystemen wie Coq und Agda sehr wichtig. Diese Systeme verwenden den Curry-Howard-Isomorphismus zwischen Programmen und Beweisen. Beweise über induktiv definierte Datentypen wurden traditionell unter Verwendung von Induktionsprinzipien beschrieben. Später wurde jedoch festgestellt, dass die Beschreibung eines Programms über eine rekursiv definierte Funktion mit Mustervergleich ein natürlicherer Beweis ist als die direkte Verwendung von Induktionsprinzipien. Leider führt das Zulassen nicht terminierender Definitionen zu logischen Inkonsistenzen in den Typentheorien^{[citation needed]}. Aus diesem Grund sind in Agda und Coq Terminierungsprüfer integriert.

Größenarten[edit]

Einer der Ansätze zur Terminierungsprüfung in abhängig typisierten Programmiersprachen sind Größentypen. Die Hauptidee besteht darin, die Typen, über die wir rekursieren können, mit Größenanmerkungen zu versehen und rekursive Aufrufe nur für kleinere Argumente zuzulassen. Größentypen werden in Agda als syntaktische Erweiterung implementiert.

Aktuelle Forschung[edit]

Es gibt mehrere Forschungsteams, die an neuen Methoden arbeiten, die eine (Nicht-) Beendigung anzeigen können. Viele Forscher nehmen diese Methoden in Programme auf^[2] die versuchen, das Beendigungsverhalten automatisch zu analysieren (also ohne menschliche Interaktion). Ein fortlaufender Aspekt der Forschung besteht darin, die Verwendung der vorhandenen Methoden zur Analyse des Beendigungsverhaltens von Programmen zu ermöglichen, die in Programmiersprachen der “realen Welt” geschrieben sind. Für deklarative Sprachen wie Haskell, Mercury und Prolog liegen viele Ergebnisse vor^[3][4][5] (hauptsächlich wegen des starken mathematischen Hintergrunds dieser Sprachen). Die Forschungsgemeinschaft arbeitet auch an neuen Methoden zur Analyse des Beendigungsverhaltens von Programmen, die in imperativen Sprachen wie C und Java geschrieben sind.

Aufgrund der Unentscheidbarkeit des Halting-Problems kann die Forschung auf diesem Gebiet nicht vollständig sein. Man kann sich immer neue Methoden vorstellen, die neue (komplizierte) Gründe für die Beendigung finden.

Siehe auch[edit]

Verweise[edit]

Forschungsarbeiten zur automatisierten Analyse der Programmbeendigung umfassen:

Zu den Systembeschreibungen der Tools zur automatisierten Terminierungsanalyse gehören:

• Giesl, J. (1995). “Generieren von Polynomreihenfolgen für Termination Proofs (Systembeschreibung)”. In Hsiang, Jieh (Hrsg.). Umschreibungstechniken und -anwendungen, 6. Int. Conf., RTA-95 (Nachschrift). LNCS. 914. Springer. S. 426–431.
• Ohlebusch, E.; Claves, C.; Marché, C. (2000). “TALP: Ein Tool zur Terminierungsanalyse von Logikprogrammen (Systembeschreibung)”. In Bachmair, Leo (Hrsg.). Umschreibungstechniken und -anwendungen, 11. Int. Conf., RTA-00 (komprimiertes Postskriptum). LNCS. 1833. Springer. S. 270–273.
• Hirokawa, N.; Middeldorp, A. (2003). “Tsukuba Termination Tool (Systembeschreibung)”. In Nieuwenhuis, R. (Hrsg.). Umschreibungstechniken und -anwendungen, 14. Int. Conf., RTA-03 (PDF). LNCS. 2706. Springer. S. 311–320.
• Giesl, J.; Thiemann, R.; Schneider-Kamp, P.; Falke, S. (2004). “Automated Termination Proofs mit AProVE (Systembeschreibung)”. In van Oostrom, V. (Hrsg.). Umschreibungstechniken und -anwendungen, 15. Int. Conf., RTA-04 (PDF). LNCS. 3091. Springer. S. 210–220. ISBN 3-540-22153-0.
• Hirokawa, N.; Middeldorp, A. (2005). “Tiroler Kündigungswerkzeug (Systembeschreibung)”. In Giesl, J. (Hrsg.). Term Rewriting and Applications, 16. Int. Conf., RTA-05. LNCS. 3467. Springer. S. 175–184. ISBN 978-3-540-25596-3.
• Koprowski, A. (2006). “TPA: Kündigung automatisch nachgewiesen (Systembeschreibung)”. In Pfenning, F. (Hrsg.). Term Rewriting and Applications, 17. Int. Conf., RTA-06. LNCS. 4098. Springer. S. 257–266.
• Marché, C.; Zantema, H. (2007). “Der Kündigungswettbewerb (Systembeschreibung)”. In Baader, F. (Hrsg.). Term Rewriting and Applications, 18. Int. Conf., RTA-07 (PDF). LNCS. 4533. Springer. S. 303–313.

Externe Links[edit]