Vlnění - Rippling

Vlnění[1] označuje skupinu metaúrovně heuristika, vyvinutý především ve skupině pro matematické uvažování ve škole informatiky na VŠE University of Edinburgh a nejčastěji se používá k vedení indukční důkazy v automatizované systémy prokazování vět. Vlnění lze považovat za omezenou formu přepsat systém, kde se používají speciální anotace na úrovni objektů k zajištění oplodnění po dokončení přepisování, s požadavkem snižujícím míru zajišťujícím ukončení jakékoli sady pravidel a výrazů přepsání.

Dějiny

Raymond Aubin byl první osobou, která při práci na své disertační práci z roku 1976 použila výraz „rippling out“[2] na univerzitě v Edinburghu. Během fáze přepisování indukčních důkazů poznal běžný pohybový vzor. Alan Bundy později obrátil tento koncept na hlavu tím, že definoval zvlnění jako tento vzor pohybu, spíše než jako vedlejší účinek.[Citace je zapotřebí ]

Od té doby byly vytvořeny výrazy „vlnící se do strany“, „vlnící se dovnitř“ a „vlnící se minulost“, takže termín byl zobecněn na vlnící se.[Citace je zapotřebí ] Rippling se od roku 2007 nadále vyvíjí v Edinburghu i jinde.

Zvlnění bylo aplikováno na mnoho problémů, které jsou tradičně považovány za těžké v komunitě dokazující induktivní věty, včetně Bledsoe věty o limitu[Citace je zapotřebí ] a důkaz mikroprocesoru Gordon,[Citace je zapotřebí ] miniaturní počítač vyvinutý společností Michael J. C. Gordon a jeho tým v Cambridge.

Přehled

Při pokusu dokázat propozici dostáváme velmi často zdrojový a cílový výraz, které se liší pouze zahrnutím několika dalších syntaktických prvků.

To platí zejména pro indukční důkazy, kde je daný výraz považován za induktivní hypotéza a cílový výraz induktivní závěr. Rozdíly mezi hypotézou a závěrem jsou obvykle jen malé, možná zahrnutí nástupnické funkce (např. +1) kolem indukční proměnné.

Na začátku zvlnění jsou identifikovány rozdíly mezi dvěma výrazy, známé jako vlnoplochy ve zvlněné řeči. Tyto rozdíly obvykle zabraňují dokončení důkazu a je třeba je „přesunout“. Cílový výraz je anotován, aby se rozlišily vlnové fronty (rozdíly) a kostra (společná struktura) mezi těmito dvěma výrazy. Speciální pravidla, nazývaná vlnová pravidla, lze poté použít v a ukončení způsobem manipulovat s cílovým výrazem, dokud nebude možné použít zdrojový výraz k dokončení důkazu.

Příklad

Naším cílem je ukázat, že přidání přirozená čísla je komutativní. Toto je základní vlastnost a důkaz je rutinní indukcí. Přesto může být vyhledávací prostor pro nalezení takového důkazu docela velký.

Typicky je základní případ jakéhokoli indukčního důkazu řešen jinými metodami než zvlněním. Z tohoto důvodu se soustředíme na krokový případ. Náš krokový krok má následující formu, kde jsme se rozhodli použít x jako indukční proměnnou:

Rippling step case.png

Můžeme také vlastnit několik pravidel přepisu, která jsou odvozena z lemmat, indukčních definic nebo jinde a která lze použít k vytvoření pravidel vln. Předpokládejme, že máme následující tři pravidla přepisování:

Rippling rewrite rules.png

pak mohou být anotovány, aby vytvořily:

Vlnící se vlnová pravidla.png

Všimněte si, že všechna tato anotovaná pravidla zachovávají kostru (x + y = y + x, v prvním případě a x + y ve druhém / třetím). Nyní, anotující případ indukčního kroku, nám dává:

Rippling anotated step case.png

A my jsme všichni připraveni provádět vlnění:

Rippling ripple.png

Všimněte si, že konečné přepsání způsobí zmizení všech vlnových front a k dokončení důkazu nyní můžeme použít oplodnění, použití indukčních hypotéz.

Reference

  1. ^ Alan Bundy; David Basin; Dieter Hutter; Andrew Ireland (2005). Rippling: Metaúrovňové pokyny pro matematické uvažování. Cambridge Tracts v teoretické informatice. Cambridge: Cambridge University Press. doi:10.1017 / CBO9780511543326. ISBN  0-521-83449-X.
  2. ^ Aubin, Raymond (1976), Mechanizace strukturální indukce, EDI-INF-PHD, 76-002, University of Edinburgh, hdl:1842/6649

Další čtení