Nqthm - Nqthm

Nqthm je věta prover někdy označované jako Boyer – Mooreova věta. Byl to předchůdce ACL2.[1]

Dějiny

Systém byl vyvinut společností Robert S. Boyer a J Strother Moore, profesoři informatiky na University of Texas, Austin. Začali pracovat na systému v roce 1971 v roce Edinburgh, Skotsko. Jejich cílem bylo vytvořit plně automatický tester vět založený na logice. Použili variantu Čistý LISP jako pracovní logika.

Definice

Definice jsou formovány jako úplně rekurzivní funkce, systém rozsáhle využívá přepis a indukce heuristika, která se používá při přepisování, a něco, čemu se říká symbolické hodnocení, selže.

Systém byl postaven na vrcholu Lispu a měl několik velmi základních znalostí o stavu zvaném „Ground-zero“, stavu stroje po bootstrapping na implementaci Common Lisp.

Toto je příklad důkazu jednoduché aritmetické věty. Funkce ČASY je součástí BOOT-STRAP (nazývaný „satelit“) a je definován jako

 (DEFN ČASY (X Y)  (LI (ZEROP X)      0      (PLUS Y (ČASY (SUB1 X) Y))))

Věta formulace

Formulace věty je také uvedena v Lispově podobné syntaxi:

 (dokázat-lemma komutativnost časů (přepsat)   (rovnat se (krát X z) (krát z X)))

Pokud se věta ukáže jako pravdivá, bude přidána do znalostní základny systému a může být použita jako pravidlo přepsání pro budoucí důkazy.

Samotný důkaz je podán kvazi-přirozeným jazykem. Autoři náhodně vybírají typické matematické fráze pro vložení kroků do matematického důkazu, což ve skutečnosti činí důkazy docela čitelnými. Existují makra pro Latex které mohou transformovat strukturu Lispu do více či méně čitelného matematického jazyka.

Důkaz komutativity časů pokračuje:

 Pojmenujte domněnku * 1. Budeme apelovat na indukci. V domněnce jsou termíny naznačeny dvě indukce, obě jsou chybné. Omezujeme naši úvahu na dvě navržené největším počtem neprprimativních rekurzivních funkcí v domněnce. Protože oba jsou stejně pravděpodobné, zvolíme libovolně. Indukujeme podle následujícího schématu: (AND (IMPLIES (ZEROP X) (p X Z)) (IMPLIES (AND (NOT (ZEROP X)) (p (SUB1 X) Z)) (p X Z))). Lineární aritmetika, lemma POČET-ČÍSLO a definice ZEROP nás informují, že míra (POČET X) klesá podle opodstatněného vztahu LESSP v každém indukčním kroku schématu. Výše uvedené indukční schéma vytváří následující dvě nové domněnky: Případ 2. (IMPLIES (ZEROP X) (ROVNÝ (ČASY Z) (ČASY Z X))).

a poté, co prošel řadou indukčních důkazů, to nakonec uzavírá

Případ 1. (IMPLIES (AND (NOT (ZEROP Z)) (EQUAL 0 (TIMES (SUB1 Z) 0))) (EQUAL 0 (TIMES Z 0))). To zjednodušuje a rozšiřuje definice ZEROP, TIMES, PLUS , a EQUAL, do: T. Tím se dokončí důkaz o * 1,1, který také dokončí důkaz o * 1. QED [0,0 1,2 0,5] KOMUNATIVNOST

Důkazy

Se systémem bylo provedeno nebo potvrzeno mnoho důkazů

  • (1971) seznam zřetězení
  • (1973) druh vložení
  • (1974) binární sčítač
  • (1976) překladač výrazů pro zásobníkový stroj
  • (1978) jedinečnost hlavních faktorizací
  • (1983) invertibilita šifrovacího algoritmu RSA
  • (1984) neřešitelnost problému zastavení pro Pure Lisp
  • (1985) mikroprocesor FM8501 (Warren Hunt) [2]
  • (1986) Gödelova věta o neúplnosti (Shankar)
  • (1988) CLI Stack (Bill Bevier, Warren Hunt, Matt Kaufmann, J Moore, Bill Young)
  • (1990) Gaussův zákon kvadratické vzájemnosti (David Russinoff)
  • (1992) Byzantine Generals and Clock Synchronization (Bevier and Young)
  • (1992) Kompilátor pro podmnožinu jazyka Nqthm (Arthur Flatau)
  • (1993) dvoufázový asynchronní komunikační protokol
  • (1993) Motorola MC68020 a Berkeley C String Library (Yuan Yu)
  • (1994) Věta Paříž – Harrington Ramsey (Kenneth Kunen )
  • (1996) Rovnocennost NFSA a DFSA (Debora Weber-Wulff )

PC-Nqthm

Výkonnější verze s názvem PC-Nqthm (Proof-checker Nqthm) byla vyvinuta společností Matt Kaufmann. To uživateli poskytlo kontrolní nástroje, které systém automaticky používá, aby bylo možné poskytnout důkladnější pokyny. To je skvělá pomoc, protože systém má neproduktivní tendenci bloudit nekonečnými řetězci indukčních důkazů.

Literatura

  • Příručka k výpočetní logice, R.S. Boyer a J. S. Moore, Academic Press (2. vydání), 1997.
  • The Boyer-Moore Theorem Prover and its Interactive Enhancement, s M. Kaufmann a R. S. Boyer, Computers and Mathematics with Applications, 29 (2), 1995, str. 27–62.

Ocenění

Ocenění

V roce 2005 Robert S. Boyer, Matt Kaufmann, a J Strother Moore obdržel Cena softwarového systému ACM za jejich práci na zkoušce věty Nqthm.[3]

Reference

  1. ^ „Nqthm, provokátor Boyer-Moore“.
  2. ^ Hunt jr., Warren A. (1986), FM8501: Ověřený mikroprocesor, Technická zpráva, 47, Texaská univerzita v Austinu
  3. ^ Sdružení pro výpočetní techniku, „ACM: Tisková zpráva, 15. března 2006“[trvalý mrtvý odkaz ], campus.acm.org, zpřístupněno 27. prosince 2007 (anglická verze ).

externí odkazy