Analýza ukončení - Termination analysis

prázdnota F(int n) {   zatímco (n > 1)      -li (n % 2 == 0)          n = n / 2;      jiný          n = 3 * n + 1;}

v počítačová věda, analýza ukončení je programová analýza který se pokouší zjistit, zda je hodnocení daného program zastaví pro každý vstup. To znamená určit, zda vstupní program počítá a celkový funkce.

Úzce souvisí s Zastavení problému, což je určit, zda se daný program zastaví pro a daný vstup a který je nerozhodnutelný. Analýza ukončení je ještě obtížnější než problém zastavení: analýza ukončení v modelu Turingovy stroje protože model programů implementujících vypočítatelné funkce by měl za cíl rozhodnout, zda je daný Turingův stroj a celkem Turingův stroj, a tento problém je na úrovni ${displaystyle Pi _ {2} ^ {0}}$ z aritmetická hierarchie a je tedy přísně obtížnější než problém zastavení.

Nyní otázka, zda je vypočítatelná funkce celková, není částečně rozhodnutelný ^[1], každý zvuk analyzátor ukončení (tj. kladná odpověď není nikdy poskytnuta pro nekončící program) je neúplný, tj. musí selhat při určování ukončení pro nekonečně mnoho ukončovacích programů, ať už navždy spuštěním nebo zastavením s neurčitou odpovědí.

Doklad o ukončení

A důkaz ukončení je typ matematický důkaz který hraje v formální ověření protože úplná správnost z algoritmus záleží na ukončení.

Jednoduchá obecná metoda pro konstrukci důkazů o ukončení zahrnuje přidružení a opatření s každým krokem algoritmu. Opatření je převzato z domény a opodstatněný vztah, jako například z řadové číslovky. Pokud se míra „snižuje“ podle vztahu v každém možném kroku algoritmu, musí se ukončit, protože neexistují žádné nekonečné sestupné řetězy s ohledem na opodstatněný vztah.

Některé typy analýzy ukončení mohou automaticky generovat nebo naznačovat existenci důkazu o ukončení.

Příklad

Příklad a programovací jazyk konstrukt, který může nebo nemusí ukončit, je a smyčka, protože je lze spustit opakovaně. Smyčky implementované pomocí a proměnná čítače jak se obvykle nachází v zpracování dat algoritmy obvykle končí, což prokazuje pseudo kód příklad níže:

i: = 0smyčka dokud i = SIZE_OF_DATA data procesu (data [i])) // zpracovat datový blok na pozici i    i: = i + 1 // přejít na další část dat, která mají být zpracována

Pokud je hodnota SIZE_OF_DATA je nezáporná, pevná a konečná, smyčka nakonec za předpokladu, že bude ukončena process_data končí také.

Je možné ukázat, že některé smyčky vždy končí nebo nikdy nekončí lidskou kontrolou. Například následující smyčka se teoreticky nikdy nezastaví. Může se však zastavit při spuštění na fyzickém stroji kvůli aritmetické přetečení: buď vedoucí k výjimka nebo způsobí, že se čítač zalomí na zápornou hodnotu a umožní splnění podmínky smyčky.

i: = 1smyčka dokud i = 0 i: = i + 1

Při analýze ukončení se také můžete pokusit určit chování ukončení některého programu v závislosti na neznámém vstupu. Následující příklad ilustruje tento problém.

i: = 1smyčka dokud i = NEZNÁMÉ i: = i + 1

Zde je podmínka smyčky definována pomocí nějaké hodnoty UNKNOWN, kde hodnota UNKNOWN není známa (např. Definována vstupem uživatele při spuštění programu). Zde analýza ukončení musí brát v úvahu všechny možné hodnoty NEZNÁMÉ a zjistit, že v možném případě NEZNÁMÉ = 0 (jako v původním příkladu) nelze ukončení zobrazit.

Neexistuje však žádný obecný postup pro určení, zda se výraz zahrnující instrukce smyčky zastaví, i když jsou lidé pověřeni kontrolou. Teoretickým důvodem je nerozhodnutelnost problému zastavení: nemůže existovat nějaký algoritmus, který určuje, zda se daný program zastaví po konečně mnoha výpočetních krocích.

V praxi se nepodaří zobrazit ukončení (nebo neukončení), protože každý algoritmus pracuje s konečnou sadou metod, které jsou schopny extrahovat relevantní informace z daného programu. Metoda by se mohla podívat na to, jak se proměnné mění s ohledem na některou podmínku smyčky (možná ukazuje ukončení této smyčky), jiné metody se mohou pokusit převést výpočet programu na nějaký matematický konstrukt a pracovat na tom, případně získat informace o chování ukončení z některé vlastnosti tohoto matematického modelu. Ale protože každá metoda je schopna „vidět“ pouze některé konkrétní důvody pro (ne) ukončení, i přes kombinaci těchto metod nelze pokrýt všechny možné důvody pro (ne) ukončení.^{[Citace je zapotřebí ]}

Rekurzivní funkce a smyčky jsou ekvivalentní ve výrazu; jakýkoli výraz zahrnující smyčky lze zapsat pomocí rekurze a naopak. Tak ukončení rekurzivních výrazů je také obecně nerozhodnutelný. Většina rekurzivních výrazů nalezených v běžném používání (tj. Ne patologické ) lze prokázat, že končí různými způsoby, obvykle v závislosti na definici samotného výrazu. Jako příklad lze uvést argument funkce v rekurzivním výrazu pro faktoriál funkce níže se vždy sníží o 1; podle dobře objednávající nemovitost z přirozená čísla, argument nakonec dosáhne 1 a rekurze bude ukončena.

funkce faktoriál (argument tak jako přirozené číslo) -li argument = 0 nebo argument = 1 vrátit se 1    v opačném případě        vrátit se argument * faktoriál (argument - 1)

Závislé typy

Kontrola ukončení je v systému Windows velmi důležitá závisle napsané programovací jazyk a věty prokazující systémy jako Coq a Agda. Tyto systémy používají Curry-Howardův izomorfismus mezi programy a důkazy. Důkazy nad indukčně definovanými datovými typy byly tradičně popsány pomocí indukčních principů. Později však bylo zjištěno, že popis programu pomocí rekurzivně definované funkce s porovnáváním vzorů je přirozenější způsob dokazování než přímé použití indukčních principů. Povolení nedefinujících definic bohužel vede k logické nekonzistenci v teoriích typů^{[Citace je zapotřebí ]}. Proto Agda a Coq mít zabudované nástroje pro ukončení.

Velikostní typy

Jedním z přístupů ke kontrole ukončení v závislých typových programovacích jazycích jsou velké typy. Hlavní myšlenkou je anotovat typy, nad kterými můžeme opakovaně používat anotace velikosti a povolit rekurzivní volání pouze na menších argumentech. Velikostní typy jsou implementovány v Agda jako syntaktická přípona.

Aktuální výzkum

Existuje několik výzkumných týmů, které pracují na nových metodách, které mohou ukázat (ne) ukončení. Mnoho vědců zahrnuje tyto metody do programů^[2] kteří se snaží analyzovat chování ukončení automaticky (tedy bez lidské interakce). Pokračujícím aspektem výzkumu je umožnit použití stávajících metod k analýze ukončovacího chování programů napsaných v programovacích jazycích „reálného světa“. Pro deklarativní jazyky jako Haskell, Rtuť a Prolog existuje mnoho výsledků^[3][4][5] (hlavně kvůli silnému matematickému pozadí těchto jazyků). Výzkumná komunita také pracuje na nových metodách analýzy chování ukončení programů napsaných v imperativních jazycích, jako jsou C a Java.

Vzhledem k nerozhodnutelnosti problému zastavení zastavení nelze v této oblasti dosáhnout úplnosti. Vždy lze uvažovat o nových metodách, které nacházejí nové (komplikované) důvody ukončení.

Viz také

• Analýza složitosti - problém odhadnout čas potřebný k ukončení
• Varianta smyčky
• Totální funkční programování - paradigma programování, které omezuje rozsah programů na ty, které prokazatelně končí
• Waltherova rekurze

Reference

Výzkumné práce týkající se automatizované analýzy ukončení programu zahrnují:

• Christoph Walther (1988). „Argumentem ohraničené algoritmy jako základ pro automatizované důkazy o ukončení“. Proc. 9 Konference o automatizovaném odpočtu. LNAI. 310. Springer. 602–621.
• Christoph Walther (1991). „O prokázání strojového ukončení algoritmů“ (PDF). Umělá inteligence. 70 (1).
• Xi, Hongwei (1998). "Směrem k důkazům o automatizovaném ukončení Zmrazení" (PDF). v Tobias Nipkow (vyd.). Techniky a aplikace přepisování, 9. Int. Konf., RTA-98. LNCS. 1379. Springer. str. 271–285.
• Jürgen Giesl; Christoph Walther; Jürgen Brauburger (1998). "Analýza ukončení funkčních programů". W. W. Bibel; P. Schmitt (eds.). Automatizovaný odpočet - základ pro aplikace (postscript). 3. Dordrecht: Kluwer Academic Publishers. str. 135–164.
• Christoph Walther (2000). "Kritéria pro ukončení". V S. Hölldobler (ed.). Intelektika a výpočetní logika (postscript). Dordrecht: Kluwer Academic Publishers. 361–386.
• Christoph Walther; Stephan Schweitzer (2005). „Automatizovaná analýza ukončení pro neúplně definované programy“ (PDF). U Franze Baadera; Andrei Voronkov (eds.). Proc. 11. Int. Konf. na Logika pro programování, umělou inteligenci a uvažování (LPAR). LNAI. 3452. Springer. 332–346.
• Adam Koprowski; Johannes Waldmann (2008). „Arktické ukončení ... pod nulou“. V Andrei Voronkov (ed.). Techniky a aplikace přepisování, 19. Int. Konf., RTA-08 (PDF). Přednášky z informatiky. 5117. Springer. 202–216. ISBN  978-3-540-70588-8.

Systémové popisy nástrojů pro automatizovanou analýzu ukončení zahrnují:

• Giesl, J. (1995). Msgstr "Generování polynomiálních objednávek pro důkazy o ukončení (popis systému)". V Hsiang, Jieh (ed.). Techniky a aplikace přepisování, 6. Int. Konf., RTA-95 (postscript). LNCS. 914. Springer. 426–431.
• Ohlebusch, E .; Claves, C .; Marché, C. (2000). "TALP: Nástroj pro analýzu ukončení logických programů (popis systému)". V Bachmair, Leo (ed.). Techniky a aplikace přepisování, 11. Int. Konf., RTA-00 (komprimovaný postscript). LNCS. 1833. Springer. 270–273.
• Hirokawa, N .; Middeldorp, A. (2003). "Tsukuba Termination Tool (popis systému)". V Nieuwenhuis, R. (ed.). Techniky a aplikace přepisování, 14. Int. Konf., RTA-03 (PDF). LNCS. 2706. Springer. 311–320.
• Giesl, J .; Thiemann, R .; Schneider-Kamp, P .; Falke, S. (2004). Msgstr "Automatizované důkazy o ukončení s AProVE (popis systému)". V van Oostrom, V. (ed.). Techniky a aplikace přepisování, 15. Int. Konf., RTA-04 (PDF). LNCS. 3091. Springer. 210–220. ISBN  3-540-22153-0.
• Hirokawa, N .; Middeldorp, A. (2005). Msgstr "Tyrolský nástroj pro ukončení (popis systému)". V Giesl, J. (ed.). Přepisování termínů a aplikace, 16. Int. Konf., RTA-05. LNCS. 3467. Springer. 175–184. ISBN  978-3-540-25596-3.
• Koprowski, A. (2006). Msgstr "TPA: Automaticky prokázáno ukončení (popis systému)". V Pfenning, F. (ed.). Přepisování termínů a aplikace, 17. Int. Konf., RTA-06. LNCS. 4098. Springer. 257–266.
• Marché, C .; Zantema, H. (2007). "Soutěž o ukončení (popis systému)". V Baader, F. (ed.). Přepisování termínů a aplikace, 18. Int. Konf., RTA-07 (PDF). LNCS. 4533. Springer. 303–313.

externí odkazy

• Analýza ukončení funkčních programů vyšších řádů
• Seznam adres pro ukončení nástrojů
• Ukončení soutěže - viz Marché, Zantema (2007)
• Ukončovací portál