Päätettävyys

Tässä artikkelissa käsitellään termin "päätettävyys" erityisiä merkityksiä matematiikassa ja tietojenkäsittelytieteessä . Katso yleisempi lähestymistapa päätöksestä .

In matemaattinen logiikka , termi ratkeavuuden kattaa kaksi liittyviä käsitteitä: looginen ratkeavuuden ja algoritmeihin ratkeavuuden .

Epäröinti on negaatio ratkeavuuden. Molemmissa tapauksissa kyseessä on ajatuksen virallistaminen, jota emme voi aina päätellä, kun kysymme itseltämme, vaikka se olisikin loogisessa muodossa.

Lausunnon ratkaistavuus, ratkaisemattomuus loogisessa järjestelmässä

Väitelause (sanomme julkilausuma) sanotaan olevan ratkeava käytettäessä itsestään selvää teoriassa , jos voidaan osoittaa, tai sen negaatio osoitti puitteissa tätä teoriaa. Matemaattinen lausunto on siis teoriassa ratkaisematon, jos sitä on mahdotonta päätellä tai johtaa sen kieltämistä tämän teorian aksiomeista. Tämän erottamattomuuden käsitteen erottamiseksi algoritmisen päättämättömyyden käsitteestä (katso alla) sanotaan myös, että lausunto on riippumaton aksioomajärjestelmästä. Tämä pätee erityisesti kanssa Euklideen kuuluisan postulate yhtäläisyyksiä , suhteessa sen geometriaa , tai vaikka hypoteesi jatkumoa suhteellisen kuin tavanomaiset teoria , jonka mukaan ei ole kardinaali välillä että l. Joukko luonnollisia numeroita ja että n reaalilukujen joukko , joka Paul Cohen osoitti vuonna 1963 olevan undecidable.

Vuonna klassisen logiikan mukaan täydellisyyden lauseen , on ehdotus on ratkeamaton on teoriassa jos on malleja teoriaa, jossa ehdotus on väärä ja malleja, joissa se on totta. Mallit käytetään usein osoittamaan, että lausunto on riippumaton järjestelmä aksioomat (tässä yhteydessä, suosimme riippumaton sen sijaan undecidable ). Tässä tapauksessa käytetty ominaisuus ei ole täydellisyyslauseke, vaan sen päinvastoin, hyvin välitön, kutsutaan korjauslauseeksi . Luultavasti tämä muuten ensimmäinen ulkonäkö käsite malli, jossa rakentaminen XIX : nnen vuosisadan malleja Epäeuklidinen geometriat , eikä tarkkailun aksioomasta yhtäläisyyksiä. Jos myönnämme tosiasian, melko intuitiivinen, että euklidinen geometria on johdonmukainen - rinnakkaisuuksien aksioman negaatiota ei johdeta muista aksiomeista - rinnakkaisuuksien aksioma on todellakin riippumaton geometrian muista aksiomeista tai muuten järjestelmässä ratkaisematon muodostuu jäljellä olevista aksiomeista.

Matemaattinen teoria , jolle lausunnot on ratkeava sanotaan olevan täydellistä , muuten se sanotaan olevan puutteellinen . Monet matemaattiset teoriat ovat epätäydellisiä, koska on olemassa teorian kielellä ilmaistavia lausuntoja, joita aksiomit (ryhmien teoria, renkaat ...) eivät määrää. Tiettyjä teorioita, kuten teoria algebrallisesti suljettu kentät on tietyn ominaisuuden , että suljetun todellinen kenttiä , tai jopa Presburger n aritmeettinen , ovat täydellisiä. Epätäydellisyys teoreema on Gödel takuuta siitä itsestään selvää teoriaa johdonmukaisesti, ja tarpeeksi tehokas edustamaan Peanon aritmeettinen (tavanomainen aritmeettinen) on puutteellinen, jos se on axiomatized jotta voimme päättää algoritminen merkityksessä (katso alla), vai ei lausuma on aksioma. Tämä viimeinen hypoteesi, joka näyttää hieman monimutkaiselta lausua, on hyvin luonnollinen ja vahvistettu matematiikan tavallisilla aksiomaattisilla teorioilla .

Päätösongelman ratkaisukelpoisuus, algoritminen päättämättömyys

Määritelmä

Päätösongelmalla sanotaan olevan ratkeava , jos on olemassa algoritmi , mekaaninen menettely, joka päättyy äärellinen määrä vaiheita, joka päättää siitä, toisin sanoen, jossa vastataan kyllä tai ei kysymykseen., Joita ongelma. Jos ei ole tällaisia algoritmeja, ongelma on sanottu olevan undecidable . Esimerkiksi pysähtymisongelma on ratkaisematon . Voimme muodostaa algoritmilla tai mekaanisella menettelyllä laskettavan funktion käsitteen eri tavoin, esimerkiksi käyttämällä Turingin koneita . Kaikki käytetyt menetelmät osoittautuivat vastaaviksi heti, kun ne olivat riittävän yleisiä, mikä on argumentti kirkon teesille: mekaanisella menettelyllä laskettavat toiminnot ovat todellakin ne, jotka lasketaan yhden näistä laskennallisista malleista. Kirkon opinnäytetyö on välttämätöntä tulkita odotetulla tavalla todiste päättämättömyydestä.

Jos mikään mekaaninen prosessi tai algoritmi ei pysty vastaamaan kysymykseen, voimme puhua algoritmisesta päättämättömyydestä erottaaksemme tämän käsityksen edellisessä kappaleessa paljastetusta loogisesta päättämättömyydestä (tai joskus Turingin merkityksellisestä algoritmisen päätettävyyden ja siinä mielessä päätettävyydestä Gödelin looginen päätettävyys).

Pieni selvennys on ehkä välttämätön: Sanominen ongelman ratkaisemattomuudesta ei tarkoita sitä, että esitetyllä kysymyksellä ei ole eikä tule koskaan olemaan ratkaisua, vaan vain sitä, että ei ole olemassa yhtä ainoaa menetelmää. Ja hyvin määritelty, mekaanisesti sovellettava vastaus kysymys.

Päätettävät ja ratkaisemattomat sarjat

Luonnollisten kokonaislukujen alajoukon sanotaan olevan ratkaistavissa, kun ongelma siitä, kuuluuko jokin kokonaisluku tähän joukkoon, on ratkaistavissa, muuten ratkaisematon. Yleistämme suoraan kokonaislukujoukkoihin. Sanomme myös lopullisesta joukosta, että se on rekursiivinen . Päätettävän joukon komplementti on päätettävissä. Näytämme laskettavuusteoriassa, että rekursiivisesti numeroituva joukko, jonka komplementti on rekursiivisesti numeroitava, on rekursiivinen (ts. Ratkaistavissa).

Nämä käsitteet on yleistetty virallisille kielille koodaamalla "à la Gödel" . Ne on myös mahdollista määritellä suoraan. Loogisten teorioiden tapauksessa (suljettu, siis vähennyksen avulla) puhumme sitten päätettävästä teoriasta tai ratkaisemattomasta teoriasta . Näitä käsitteitä ei pidä sekoittaa edellisessä kappaleessa esitettyihin täydellisen teorian ja puutteellisen teorian käsitteisiin . Kun puhumme ratkaistavasta tai ratkaisemattomasta teoriasta, on väistämättä kysymys algoritmisesta päätettävyydestä eikä koskaan loogisesta päätettävyydestä. Päinvastoin, kun puhumme päätettävistä tai ratkaisemattomista lausunnoista tai ehdotuksista, kyseessä on väistämättä looginen päätettävyys.

Esimerkkejä ratkaistavista sarjoista ja ongelmista

Kaikki kokonaislukujen äärelliset alajoukot ovat päätettävissä (riittää, että testataan joukon jokaisen kokonaisluvun tasa-arvo). Voimme rakentaa algoritmin päättää, onko luonnollinen kokonaisluku tasainen vai ei (jaamme kahdella, jos loppuosa on nolla, luku on parillinen, jos loppuosa on yksi, se ei ole), joten l numerot on ratkaistavissa; se on sama alkulukujoukolle . Huomaa, että joukko voi olla teoreettisesti päätettävissä ilman käytännössä päätöksen tekemistä, koska se vaatii liian paljon aikaa (enemmän kuin maailmankaikkeuden ikä) tai liian paljon resursseja (enemmän kuin universumin d-atomien lukumäärä) . Algoritmien monimutkaisuuden teorian tarkoituksena on tutkia päätösongelmia ottamalla huomioon resurssit ja laskenta-aika.

Ongelma tietää, onko propositio totta Presburgerin aritmeettisessa , toisin sanoen luonnollisten kokonaislukujen teoriassa, jossa on summa, mutta ilman kertolaskua, on ratkaistavissa.

Esimerkkejä ratkaisemattomista ongelmista

Undecidability Pysäytyslaitteen ongelman osoitettiin Alan Turing vuonna 1936. Ei ole algoritmi, jonka avulla voimme päättää, koska tahansa Turingin kone ja tulosana, laskenta, että se pysähtyy tai ei. Koska kirkon gradu , tämä tulos on hyvin yleinen. Tietojenkäsittelytieteen ilmaantumisen jälkeen sitä voidaan tulkita seuraavasti: Ei ole olemassa ohjelmaa, joka mahdollistaisi minkään riittävän tehokkaan kielen tietokoneohjelman , kuten kaikkien käytännössä käytettyjen, testaamisen , jotta voidaan joka tapauksessa päätellä , pysähtyykö se rajallinen aika tai silmukka ikuisesti.
Yleisemmin Ricen lauseessa todetaan, että kaikki tietokoneohjelmien kysymykset, jotka riippuvat vain laskutoimituksen tuloksesta (päättyykö vai eivät, laskettu arvo jne.), Ovat ratkaisemattomia tai triviaalia (tässä "triviaalilla" tarkoitetaan vastausta on aina sama (kyllä tai ei) riippumatta ohjelmasta).
Kysymys siitä, onko ensimmäisen asteen logiikan lausuma yleisesti pätevä (osoitettavissa missä tahansa teoriassa), riippuu valitusta kielen allekirjoituksesta (operaatio- tai suhdesymbolit ...). Tämä ongelma, jota kutsutaan päätös ongelma , on ratkeamaton kielen aritmeettinen, ja yleisemmin minkä tahansa ensimmäisen kertaluvun tasa-arvoinen kieli, joka sisältää ainakin yhden binäärirelaatio symbolin (kuten <tai ∈). Ensimmäisen asteen tasa-arvoinen kieli, joka sisältää vain unaarisia predikaattisymboleita (monadisten tasa-arvoisten predikaattien laskenta), on ratkaistavissa.
Kysymys siitä, onko aritmeettisella kielellä (joka vaatii molemmat operaatiot, + ja ×) esitetyn proposition totta aritmeettisen vakiomallissa, ei voida ratkaista (se on seurausta Gödelin epätäydellisyyden ensimmäisestä lauseesta tai Tarskin lause ).
Lausunnon todistettavuus Peanon aritmeettisen aksiooman perusteella on ratkaisematon (katso päätösongelma ). Gödel on osoittanut, että tämä sarja sisältyy ehdottomasti edelliseen. Koska Peanon aksiomaattisissa aksioomissa on ääretön määrä, tämä ei johdu suoraan kielipäätösongelman ratkaisemattomuudesta, kuten aiemmin todettiin. Nämä kaksi tulosta voidaan päätellä tiettyjen ehtojen täyttävien aritmeettisten teorioiden yleisestä tuloksesta. Peanon aritmeikka täyttää nämä ehdot, mutta myös Robinsonin aritmeettinen Q, jolla on rajallinen määrä aksioomia.
Todistettavuudesta lausuntoa aksioomat johdonmukaisesta teoria, ja yleisemmin minkä tahansa johdonmukaisen teorian, joka mahdollistaa ilmaista "riittävän" muodollinen aritmeettinen on ratkeamaton (ks päätös ongelma ).
Kysymys siitä, onko Diophantine-yhtälöllä ratkaisu vai ei . Todiste sen päättämättömyydestä on Matiyasevichin (1970) lause .
Kysymys siitä, ovatko lambda-laskennan kaksi termiä β-ekvivalentteja vai vastaavasti, kombinatorisen logiikan kahden termin identiteetti . Alonzon kirkko on osoittanut sen päättämättömyyden .
Post kirjeenvaihto Ongelma on ratkeamaton.

Ratkaistavat teoriat

Axiomatic teoria on ratkeava, jos on olemassa algoritmi, joka vastaa aina kyllä tai ei kysymykseen, onko tietty väite on todistettavissa tässä teoriassa. Tällainen algoritmi voidaan helposti laajentaa muodolliseksi todistushakualgoritmiksi (sillä ehdolla, jonka "tavalliset" teoriat vahvistavat, että tosiasia aksioomana on ratkaistavissa): kun tiedämme, että lausunto on osoitettavissa, riittää, kun luetellaan kaikki hyvin muotoillut todisteet, kunnes todiste tästä lausunnosta löytyy. Tämä hakualgoritmi on tietysti vain teoreettisen mielenkiinnon kohteena, lukuun ottamatta erityisen yksinkertaisia tapauksia.

Vaikka teoria on ratkaistavissa, sen päätöksen algoritminen monimutkaisuus voi olla lamauttava.

Esimerkkejä ratkaistavista teorioista:

suljettujen reaalikenttien teoria , jossa on kvantifikaattoreiden eliminointiin perustuvia algoritmeja , jotka tuottavat lauseen kannalta vastaavan lausekkeen ilman kvantteja ∀ tai ∃; lausumat ilman teorian määrittelijöitä ovat triviaalisesti päätettävissä; tunnettujen algoritmien monimutkaisuus on suuri ja sallii vain hyvin yksinkertaisten lauseiden päättämisen;
aritmeettinen Presburger (kokonaisluku aritmeettinen ilman kertolasku, tai, mikä merkitsee samalla, rajoitettu lisääntyminen tapauksessa operandi on vakio).

Looginen päätettävyys ja algoritminen päätettävyys

Molemmat käsitteet päätöksenteosta tulkitsevat intuitiivisen päätöksen käsitteen selvästi erilaisissa merkityksissä. Ne ovat kuitenkin yhteydessä toisiinsa.

Matematiikassa todellakin katsotaan, että todistuksen, jos sen löytäminen voi olla vaikeaa, on oltava "helppo" tarkistaa hyvin epävirallisessa (ja kiistanalaisessa - mutta tämä ei ole tämän artikkelin kohde) mielessä. Kun virallistamme, käännämme tämän pyytämällä, että ongelman tunnistaminen, onko lauseiden kokoonpano muodollinen esittely, on ratkaistavissa. Jotta tämä olisi oikein, on oletettava, että teorian aksioomien joukko on ratkaistavissa, mikä, kuten jo mainittiin, on hyvin luonnollista. Tämän hypoteesin mukaan teorian lausejoukko muuttuu rekursiivisesti lueteltavaksi ; tällainen teoria, jos se on täydellinen, on sitten ratkaistavissa (katso artikkelin aksiomaattisesta teoriasta lisätietoja ja perusteluja).

Toisaalta päätettävä teoria ei välttämättä ole täydellinen. Siten algebrallisesti suljettujen kenttien teoria ei ole täydellinen, koska ominaisuutta ei ole määritelty: näin ollen ensimmäisen kertaluvun lause 1 + 1 = 0 ei ole teorian seuraus, koska on kenttiä, jotka on algebrallisesti suljettu ominaisuuksilla, jotka poikkeavat toisistaan ja Ensimmäisen kertaluvun lauseke 1 + 1 ≠ 0 ei myöskään ole, koska ominaisuudelle 2 on algebrallisesti suljettuja kenttiä. Algebraan suljettujen kenttien teoria on kuitenkin ratkaistavissa. Tietyn ominaisuuden algebrallisesti suljettujen kenttien teoria on toisaalta täydellinen ja ratkaistavissa.

Totuus ja päätettävyys

Jotta näitä kahta käsitettä voidaan verrata hyödyllisesti, totuuden käsite on määriteltävä tarkasti; tämän muotoili Alfred Tarski . (Ensimmäisen asteen) logiikassa sanomme, että lause on tosi tietyssä teoriamallissa , jos sen tyydyttävät (teknisessä mielessä, mutta melko intuitiivisesti) tämän mallin objektit; esitetty lausunto on tietysti totta missä tahansa mallissa, ja johdonmukaisen teorian osalta päinvastoin päinvastoin: se on Gödelin täydellisyyslause . Tilanne on selvästi monimutkaisempi sellaisten lausuntojen osalta, joita ei voida ratkaista: on olemassa malleja, joissa ne ovat totta, ja malleja, joissa ne ovat väärät (tällaisten mallien esittäminen on lisäksi yksi klassisista tavoista todistaa ratkaisemattomuus), ja suurimmaksi osaksi ei ole mitään argumenttia, joka mahdollistaisi yhden tapauksen suosimisen toiseen; tämä on esimerkiksi geometriassa rinnakkaisten aksiomien tapaus . Aritmeettisilla lausekkeilla on kuitenkin erityinen tila: lauseke, jonka muoto on "minkä tahansa kokonaisluvun n , P (n) on tosi" (esimerkiksi " n > 5 on kolmen alkuluvun summa"), jos se on ratkaisematon, on välttämättä true (joukossa "naiiveja" kokonaislukuja, joita usein kutsutaan vakiolukuiksi ), koska muuten vastanäyte antaisi tehokkaan esityksen sen negaatiosta. Tämän havainnon perusteella Stephen Cole Kleene kehitti kokonaisen herkän loogisen teorian, aritmeettisen hierarkian tutkimuksen .

Huomautuksia ja viitteitä

Euclid , Elements , kirja I , postulaatti 5.
Tämä näkyy helposti Vaughtin lauseessa , esimerkiksi Chang ja Keisler 1990 , s. 139-140 tai luentojen ja Elisabeth Bouscaren Paris-Sud.
Chang ja Keisler 1990 , s. 344.
Ilmoitettu Chang ja Keisler 1990 , s. 43, luvun 5 harjoitus.
Rabin ja Fischer osoittivat vuonna 1974, että millä tahansa Presburgerin aritmeettisen päätöksen algoritmilla on pahin tapaus, jonka toteutusaika on suurempi kuin vakion c > 0 kohdalla. $2 ^ {{2 ^ {{cn}}}}$
Tämä on ensiluokkainen logiikka. Jokaiselle alkuluvulle p todetaan, että kentällä on ominaisuus p , ensimmäisessä järjestyksessä yhdellä ainoalla aksiomalla, jonka muoto on 1 +… + 1 = 0. Ominaisuudelle 0 tarvitaan aksiomien äärettömyys (kaikki negatiivit) edellisistä).
Päätettävyys osoitettiin poistamalla kvantifikaattorit , Alfred Tarski vuonna 1948 julkaisussa A Method Method for Elementary Algebra and Geometry , Chang ja Keisler 1990 , s. 58.

Katso myös

Bibliografia

Olivier Carton , Muodolliset kielet, laskettavuus ja monimutkaisuus ,2008[ yksityiskohdat painoksesta ] ( lue verkossa )
Jean-Michel Autebert, Laskettavuus ja päätettävyys, Dunod, 1992 ( ISBN 978-2225826320 )
Pierre Wolper , Johdatus laskettavuuden , 3 e ed., Dunod, 2006 ( ISBN 978-2100499816 )
(en) CC Chang ja H. Jerome Keisler , Model Theory , Amsterdam / New York / New York, NY, USA, Elsevier, Coll. "Logiikan ja matematiikan perusteet",1990, 3 ja toim. ( 1 st toim. 1973) ( ISBN 978-0-444-88054-3 , lukea verkossa )

Aiheeseen liittyvät artikkelit

Tarskin ongelma eksponentiaalifunktiossa (sisään)
Luettelo lausekkeista, joita ei voida ratkaista ZFC: ssä (en)
Gödelin koodaus
Gödelin epätäydellisyyslauseet

Ulkoinen linkki

"Laskennan teoreettiset rajat. Undecidable ongelmat” Cycle kolme oppituntia antaman Jean-François Raskin, Samuel Fiorini ja Gilles Geeraerts klo Belgian College on kuninkaallisen tiedeakatemian Kirjaimet ja Kuvataideakatemian Belgian .