Vikipedio:Projekto matematiko/Aŭtomata pruvado de teoremoj
El Vikipedio
 |
Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Aŭtomata pruvado de teoremoj (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi. |
Aŭtomata pruvado de teoremoj (nun la plej grava subkorpo de aŭtomatis (racianta, rezonanta, kaŭzanta)) estas la pruvanta de matematika (teoremoj, teoremas) per komputila programo. Dependanta sur la suba logiko, la problemo de decidanta la vereco de teoremo (varias, ŝanĝiĝas) de bagatela al neebla. Por la ofta (kesto, okazo) de propona logiko, la problemo estas decidebla sed NP-pleneco, kaj de ĉi tie nur eksponenta funkcio-tempo (algoritmoj, algoritmas) estas kredita al ekzisti por ĝenerala pruvanta (taskoj, taskas). Por logiko de la unua orda ĝi estas rekursie numerigebla, kio estas, donita nebarita (rimedo, rimedoj, rimedas), (ĉiu, iu) valida teoremo povas eble esti pruvita. Malvalida (propozicioj, frazoj, ordonoj), kio estas (formuloj, formulas) (tiu, ke, kiu) estas ne sekvigita per donita teorio, ne povas ĉiam esti agnoskita. En ĉi tiuj (okazoj, skatoloj, kestoj, kestas, okazas), unua-(mendi, ordo) teoremo _prover_ (majo, povas) manki al fini dum serĉanta por pruvo. Malgraŭ ĉi tiuj teoriaj limigoj, praktika teoremo _provers_ povas solvi multaj peza (problemoj, problemas) en ĉi tiuj (logikoj, logikas).
Pli simpla, sed rilatanta problemo estas pruvo (priprograma pruv(ad)o, kontrolo), kie ekzistanta pruvo por teoremo estas jesigita valida. Por ĉi tiu, ĝi estas ĝenerale postulita (tiu, ke, kiu) ĉiu persona pruvo (ŝtupo, paŝi) povas esti kontrolita per primitivo rekursie funkcio aŭ programo, kaj de ĉi tie la problemo estas ĉiam decidebla.
Interaga teoremo _provers_ postuli homa uzanto al doni aludas al la sistemo. Dependanta sur la grado de aŭtomacio, la _prover_ povas esence reduktiĝi al pruva kontrolisto, kun la uzanto provizanta la pruvo en formala vojo, aŭ grava pruvo (taskoj, taskas) povas esti (aperita, plenumita) aŭtomate. Interaga _provers_ estas uzitaj por (diversaj, diversaĵo) de (taskoj, taskas), sed (eĉ, ebena, para) plene aŭtomataj sistemoj havi jam pruvita nombro de (interezanta, interesanta) kaj peza (teoremoj, teoremas), inkluzivanta iu (tiu, ke, kiu) havi _eluded_ homo (matematikistoj, matematikistas) delonge. Tamen, ĉi tiuj sukcesoj estas sporada, kaj laboro sur peza (problemoj, problemas) kutime postulas kompetenta uzanto.
Alia distingo estas iam desegnita inter teoremo pruvanta kaj aliaj teknikoj, kie procezo estas (konsiderita, konsideris) al esti teoremo pruvanta se ĝi konsistas de tradicia pruvo, startanta kun (aksiomoj, aksiomas) kaj produktanta nova konkludo (ŝtupoj, ŝtupas, paŝas) uzantaj reguloj de konkludo. Aliaj teknikoj devus inkluzivi modela kontrolado, kiu estas ekvivalento al bruto-forta numerado de multaj eblaj ŝtatoj (kvankam la reala realigo de modelo (damoj, damludo) postulas multa _cleverness_, kaj ne simple redukti al brutforta metodo). Estas hibridaj teoremaj pruvantaj sistemoj kiu uzi modela kontrolado kiel konkluda regulo. Estas ankaŭ programoj kiu estis skribita al pruvi aparta teoremo, kun (kutime neformala) pruvo (tiu, ke, kiu) se la programo _finishes_ kun certa rezulto, tiam la teoremo estas vera. Bona ekzemplo de ĉi tiu estis la maŝino-(asistantis, helpita) pruvo de la kvar kolora teoremo, kiu estis tre kontraŭa kiel la unua pretendis matematika pruvo kiu estis esence neebla al kontroli per (homoj, homas) pro al la enorma amplekso de la programa kalkulo (tiaj pruvoj estas (nomita, vokis) ne-_surveyable_ pruvoj). Alia ekzemplo devus esti la pruvo (tiu, ke, kiu) la ludo Trakonekti Kvar estas konkeri por la unua ludanto.
Komerca uzi de aŭtomata pruvado de teoremoj estas plejparte (koncentrita, koncentriĝita) en integra cirkvita dizajno kaj (priprograma pruv(ad)o, kontrolo). Ekde la Pentium _FDIV_ cimo, la komplika flosanta punkto (unuoj, unuas) de modernaj mikroprocesoroj havi estas (dizajnita, desegnita) kun superflua _scrutiny_. En la _latest_ (proceziloj, procezas, traktiloj, traktas, procesoroj, procesoras, datumtraktiloj, datumtraktas) de AMD, Intel, kaj aliaj, aŭtomata pruvado de teoremoj havas estas kutima kontroli (tiu, ke, kiu) la dividi kaj alia (operacioj, operacias) estas (ĝusta, ĝustigi, korekti).
Enhavo |
[redaktu] Unua-(mendi, ordo) teoremo pruvanta
Unua-(mendi, ordo) teoremo pruvanta estas unu de la plej matura (subkorpoj, subkorpas) de aŭtomata pruvado de teoremoj. La logiko estas esprima sufiĉa al permesi la (specifo, specifilo) de ajna (problemoj, problemas), ofte en laŭkaŭze natura kaj intuicia vojo. Aliflanke, ĝi estas ankoraŭ duone-decidebla, kaj nombro de sono kaj plenumi kalkuloj havi estas ellaborita, kapabliganta plene aŭtomatis sistemoj. La kvalito de realigis sistemo havas beneficita per la ekzisto de granda biblioteko de norma etalono (ekzemploj, ekzemplas) (la _TPTP_), kaj ankaŭ per la _CADE_ _ATP_ Sistemo (Konkurso, Konkurenco) (_CASC_), ĉiujara (konkurso, konkurenco) de unua-(mendi, ordo) sistemoj por multaj gravaj klasoj de unua-(mendi, ordo) (problemoj, problemas).
Iu grava sistemo (ĉiuj havi gajnita almenaŭ unu _CASC_ (konkurso, konkurenco) divido) estas listita pli sube.
- E estas alta-(seanco, rendimento) _prover_ konstruita sur pure _equational_ kalkulo, ellaborita unuavice en la aŭtomatis (racianta, rezonanta, kaŭzanta) grupo de Teknika Universitato de Munkeno.
- Lutro, ellaborita je la _Argonne_ Nacia Laboratorio, estas la unua larĝe uzita alta-(seanco, rendimento) teoremo _prover_. Ĝi estas bazita sur unua-(mendi, ordo) rezolucio kaj _paramodulation_.
- _SETHEO_ estas alta-(seanco, rendimento) sistemo bazita sur la golo-direktita modela elimina kalkulo. Ĝi estas ellaborita en la aŭtomatis (racianta, rezonanta, kaŭzanta) grupo de Teknika Universitato de Munkeno. E kaj _SETHEO_ havi estas kombinita (kun aliaj sistemoj) en la _composite_ teoremo _prover_ E-_SETHEO_.
- Vampiro estas ellaborita kaj realigis je Manchester Universitato per _Andrei_ _Voronkov_, antaŭe kaj ankaŭ _Alexandre_ _Riazanov_. Ĝi havas gajnita la "monda taso por teoremo _provers_" (la _CADE_ _ATP_ (Aŭtomatis teoremo _prover_) Sistemo (Konkurso, Konkurenco)) en la plej prestiĝa _MIX_ divido por ses (jaroj, jaras) (1999, 2001 - 2005).
- _Waldmeister_ estas specialigita sistemo por unuo-_equational_ logiko de la unua ordo. Ĝi havas gajnita la _CASC_ _UEQ_ divido por la lasta naŭ (jaroj, jaras) (1997-2005).
[redaktu] Popularaj teknikoj
- Unua-(mendi, ordo) rezolucio kun samspecigo
- Apogi teoremo pruvanta
- Modela elimino
- Maniero de analitiko _tableaux_
- (Kompono, Superloko) kaj (termo, membro, flanko, termino) reverkado
- Modela kontrolado
- Matematika indukto
- Duumaj decidaj figuroj
- _DPLL_
- pli alta-(mendi, ordo) samspecigo
[redaktu] Havebla (realigoj, realigas)
- _ACL2_
- _Carine_
- _Coq_
- _CVC_ _Lite_
- E
- _Isabelle_
- Gandalf
- _HOL_
- _LCF_
- _LoTREC_
- _MetaPRL_
- _Mizar_
- _NuPRL_
- Lutro
- Paradokso
- _PhoX_
- _PVS_
- (Simpligi, Plisimpligi)
- _SPARK_ programlingvo
- _SPASS_
- Τ
- _Twelf_
- Vampiro
- _Waldmeister_
Vi povas trovi informo sur iu de ĉi tiu teoremo _provers_ kaj aliaj je http://www.tptp.org/CASC/J2/SystemDescriptions.html, aŭ la _QPQ_ retejo. La _TPTP_ biblioteko de provo (problemoj, problemas), taŭgi por (testante, testado) unua-(mendi, ordo) teoremo _provers_, estas havebla je http://www.tptp.org, kaj solvaĵoj de multaj de ĉi tiuj _provers_ por _TPTP_ (problemoj, problemas) estas en la _TSTP_ solvaĵa biblioteko, havebla je http://www.tptp.org/TSTP .
[redaktu] Grava popolo
- (Leono (Zodiako), Leono) _Bachmair_ Co-_developer_ de la superloka kalkulo.
- _Woody_ _Bledsoe_ Artefarita Inteligenteco pionira.
- _Robert_ _Stephen_ _Boyer_ Co-(Aŭtoro, Aŭtori) de la _Boyer_-_Moore_ teoremo _prover_, co-ricevanto de la _Herbrand_ Juĝo 1999.
- Vilhelmo _McCune_ _Argonne_ Nacia Laboratorio. (Aŭtoro, Aŭtori) de Lutro, la unua alta-(seanco, rendimento) teoremo _prover_. Multaj grava (paperoj, paperas), ricevanto de la _Herbrand_ Juĝo 2000.
- _Robert_ _Constable_ _Cornell_ Universitato. Grava (kotizoj, kotizas) al tipa teorio, _NuPRL_.
- _Martin_ _Davis_ (Aŭtoro, Aŭtori) de la "Gvidlibro de Artefarita (Racianta, Rezonanta, Kaŭzanta)", co-inventisto de la _DPLL_ algoritmo, ricevanto de la _Herbrand_ Juĝo 2005.
- _Branden_ _Fitelson_ Universitato de Kalifornio je _Berkeley_. Laboro en plej mallonga aksioma (bazas, bazoj) por logikaj sistemoj.
- _Harald_ _Ganzinger_ Co-_developer_ de la superloka kalkulo, kapo de la _MPI_ Saarbrücken, ricevanto de la _Herbrand_ Juĝo 2004 (postmorta).
- Miĥaelo _Genesereth_
- Miĥaelo J. C. _Gordon_ Gvidis la evoluo de la _HOL_ teoremo _prover_.
- _Donald_ W. _Loveland_ Duka Universitato. (Aŭtoro, Aŭtori), co-_developer_ de la _DPLL_-proceduro, _developer_ de modela elimino, ricevanto de la _Herbrand_ Juĝo 2001.
- _Sergei_ _Maslov_
- Normo _Megill_, _maintainer_ de _metamath_._org_, surlinia datumbazo de aŭtomate kontrolis pruvoj.
- J _Strother_ _Moore_ Co-(Aŭtoro, Aŭtori) de la _Boyer_-_Moore_ teoremo _prover_, co-ricevanto de la _Herbrand_ Juĝo 1999.
- _Robert_ _Nieuwenhuis_ Universitato de Barcelono. Co-_developer_ de la superloka kalkulo.
- _Tobias_ _Nipkow_ Teknika Universitato de Munkeno, (kotizoj, kotizas) al (pli alta-(mendi, ordo)) reverkado, co-_developer_ de la _Isabelle_ pruva asistanto
- _Ross_ _Overbeek_ _Argonne_ Nacia Laboratorio. Fondinto de La Kunularo por Interpretado de _Genomes_
- Laŭrenco C. _Paulson_ Universitato de Kembriĝo, laboro sur logiko de pli alta orda sistemo, co-_developer_ de la _Isabelle_ pruva asistanto
- Davido A. _Plaisted_ Universitato de Norda Karolino je Kapela Monteto. Kompleksecaj rezultoj, (kotizoj, kotizas) al reverkado kaj (kompletigo, plenigo), aper(aĵ)o-bazita teoremo pruvanta.
- Johano _Rushby_ Programa Surscenigisto - _SRI_ Internacia
- J. _Alan_ Robinson-a Sirakusa Universitato. Ellaborita originala rezolucio kaj samspecigo bazita unua (mendi, ordo) teoremo pruvanta, co-redaktilo de la "Gvidlibro de Aŭtomatis (Racianta, Rezonanta, Kaŭzanta)", ricevanto de la _Herbrand_ Juĝo 1996
- _Natarajan_ _Shankar_ _SRI_ Internacia, laboro sur decido (procedoj, proceduroj, proceduras), malgranda (motoroj, motoras) de pruvo, co-_developer_ de _PVS_.
- Marko _Stickel_ _SRI_. Ricevanto de la _Herbrand_ Juĝo 2002.
- _Geoff_ _Sutcliffe_ Universitato de _Miami_. _Maintainer_ de la _TPTP_ kolekto, planilo de la _CADE_ ĉiujara konkurso.
- _Robert_ _Veroff_ Universitato de Nov-Meksiko. Multaj grava (paperoj, paperas).
- _Andrei_ _Voronkov_ Co-Redaktilo de la "Gvidlibro de Aŭtomatis (Racianta, Rezonanta, Kaŭzanta)"
- _Larry_ _Wos_ _Argonne_ Nacia Laboratorio. (Lutro) Multaj grava (paperoj, paperas).
[redaktu] Referencoj ((libroj, mendas))
- Signa Logiko kaj Mekanika Teoremo Pruvanta. Mentono-_Liang_ _Chang_ kaj _Richard_ Signo-_Tung_ _Lee_. Akademia Premi (1973)
- Aŭtomatita Teoremo Pruvanta: A Logika Bazo. Fundamentaj Studoj en Komputila Scienca Volumeno 6. _Donald_ W. _Loveland_. Nordo-(Holando, Nederlando) Publikiganta (1978)
- Logiko por Komputila Scienco: Fundamentoj de Aŭtomata Teoremo Pruvanta. _Jean_ H. _Gallier_. _Harper_ & (Linio, Vico) (Eldonejoj, Eldonejas) (1986) Elŝuti
- (Principoj, Principas) de Aŭtomatita Teoremo Pruvanta. Davido A. _Duffy_. Johano _Wiley_ & (Filoj, Fas) (1991)
- Aŭtomatita (Racianta, Rezonanta, Kaŭzanta): Enkonduko kaj Aplikoj (2-a redakcio). _Larry_ _Wos_, _Ross_ _Overbeek_, _Ewing_ _Lusk_, kaj _Jim_ _Boyle_. _McGraw_-Monteto (1992)
- Gvidlibro de Aŭtomatis (Racianta, Rezonanta, Kaŭzanta) Volumeno Mi & II. _Alan_ Robinson-a kaj _Andrei_ _Voronkov_ (_eds_.) _Elsevier_ kaj _MIT_ Premi (2001)
[redaktu] Vidi ankaŭ
- Komputilo-(asistantis, helpita) pruvo
