Päätettävissä

Vuonna tietojenkäsittelyteoria , kiinteistön kutsutaan ratkeava joukkoon (myös rekursiivisesti , rekursiivisesti johdettavissa ) onko päätös menettely sitä. Päätösmenettely on algoritmi, joka voi vastata joukon jokaiselle elementille, onko sillä ominaisuus vai ei. Jos ei ”ei” tällaisia päätöksentekoprosessia, niin omaisuus on nimeltään undecidable . Päätösongelmalla on kysymys siitä, miten päätös menettelystä voidaan muotoilla tiettyä omaisuutta.

Vaikka ohjelmien tärkeimmät syntaktiset ominaisuudet ovat ratkaistavissa, Rice'in lauseen mukaan ohjelmien kaikki (ei-triviaalit) semanttiset ominaisuudet ovat ratkaisemattomat, esimerkiksi ohjelman lopettaminen tulolla ( pito-ongelma ) tai ohjelmien tasa-arvo toiminnot kaksi ohjelmaa ( vastaavuus ongelma ).

Alun perin tarkoitettu erityisesti kaavojen pätevyydelle, termiä käytetään nyt kaikkiin laskettavien joukkojen ominaisuuksiin . Algoritmin käsite edellyttää laskentamallia ; Ellei toisin mainita, tarkoitetaan Turingin koneita tai vastaavaa mallia.

määritelmä

Päätösongelman rakenne

Osajoukko numeroituvan joukko kutsutaan ratkeavia jos sen karakteristinen funktio on määritelty ${\ displaystyle T}$ ${\ displaystyle M}$ ${\ displaystyle \ chi _ {T} \ kaksoispiste M \ - {0,1 \}}$

{\ displaystyle \ chi _ {T} (t) = {\ begin {cases} 1, & {\ mbox {if t}} \ in T \\ 0, ja {\ textrm {muuten}} \ end {cases} }}

on ennustettavissa . Päätettävyyden käsite on siis jäljitetty laskettavuuden käsitteeseen.

Tässä määritelmässä oletetaan, että sarjan kaikki elementit voidaan edustaa tietokoneessa. Määrä on godelizable . Teoriassa vertailun helpottamiseksi oletetaan suoraa tai oletettavaa. Jälkimmäisessä tapauksessa ongelma on esitetty, koska sana ongelma virallisen kielen . ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle M = \ mathbb {N}}$ ${\ displaystyle M = \ {0,1 \} ^ {*}}$

Koska vain numeroituva joukko voidaan godelized käsite ratkeavuuden ei ole määritelty ja lukematon sarjaa kuten että todelliset luvut . Laskettavuuden käsitettä on kuitenkin yritetty laajentaa reaalilukuihin laajennetun konemallin avulla (esim. Blum-Shub-Smale-malli ).

Rajoitus

Undecidability ei pidä sekoittaa käytännössä tai perustavanlaatuinen mahdottomuus määrittämällä totuusarvo on selvitys . Yksityiskohtaisesti kyseessä ovat seuraavat ehdot:

Epäjohdonmukaisuus: Paradoksit tai antinomiat osoittavat, että laskurissa on ristiriitaisuuksia, eli että siinä ei ole ristiriitoja . Esimerkiksi Russellin paradoksi osoitti, että naiivi joukko teoria sisältää ristiriitoja.
Riippumattomuus: Lausumia, jotka voidaan lisätä johdonmukaiseen laskentaan luomatta ristiriitaa, kutsutaan suhteellisen vapaiksi ristiriidoista tämän laskennan suhteen. Jos sen kieltäminen on suhteellisen vapaa ristiriidoista, lausuma on riippumaton . Esimerkiksi valinnan aksioma on riippumaton Zermelo-Fraenkelin joukko-teoriasta .
Puutteellisuus: Yhdenmukaisissa laskelmissa, joilla on ainakin aritmeettisen ilmeikkyys , on tosi lauseita, joita ei voida todistaa laskelmissa. Tällaisia laskelmia kutsutaan epätäydellisiksi .

Ratkaisukyky on predikaattien eikä lausekkeiden ominaisuus. Predikaatin oletetaan olevan hyvin määritelty , joten se antaa määritetyn totuusarvon joukon kullekin elementille. Päättämättömyys tarkoittaa vain sitä, että predikaattia ei voida laskea algoritmilla.

Nollapaikan predikaatteina pidettävät lausunnot ovat aina päätettävissä, vaikka niiden totuusarvo on edelleen epäselvä. Jos lause on tosi, niin algoritmi, joka palauttaa aina yhden, on päätöksentekoprosessi. Muussa tapauksessa algoritmi, joka palauttaa aina nollan, on päätöksentekoprosessi.

historia

Päätösongelma on "ilmaisujen yleisyyden määrittämisen ongelma". "Kyse on tiettyä deduktiivista teoriaa koskevan yleisen menettelyn määrittelemisestä, jonka avulla voimme päättää, voidaanko tietty teorian sanamuotoinen lause todistaa teoriassa vai ei."

Ratkaiseva tekijä on, onko olemassa puhtaasti mekaanisesti sovellettavaa menettelyä, algoritmia , joka selvittää rajallisessa määrin vaiheita, onko lauseke, kaava voimassa järjestelmässä vai ei.

Mukaan Fregen , Whitehead ja Russell , "keskitetylle kysymys logicians ja matemaatikot oli: Onko algoritmi [...], joka määrittää mistä tahansa kaavan loogisen hammaskiven onko se seuraa tietynlaisella aksioomista tai ei (ns päätösongelma)? "

Kurt Gödel julkaisi teoksen päätösongelmasta vuonna 1931; Brittiläinen Alan Turing (1912–1954) muotoili Gödelin tulokset vuodelta 1931 teoksessaan On Computable Numbers sovelluksella ”Päätösongelmaan” (28. toukokuuta 1936), joka oli tämän matematiikan perustavanlaatuinen . Hän korvasi Gödelin yleismaailmallisen, aritmeettiseen perustuvaan viralliseen kieleen yksinkertaisilla, muodollisilla laitteilla, jotka tunnettiin nimellä Turingin kone .

Logistiikka Heinrich Scholz (1884–1956) pyysi (ja sai) kopion tästä teoksesta Turingilta vuonna 1936. Tämän työn perusteella Scholz järjesti (Achim Clausingin mukaan) "maailman ensimmäisen seminaarin tietojenkäsittelytieteestä".

Esimerkkejä

Kaikki äärelliset joukot, kaikkien parillisten numeroiden joukko ja kaikkien alkulukujen joukko ovat päätettävissä. Jokaiselle päätettävälle joukolle sen komplementti voi olla myös päätettävissä . Risteys ja liitto kahden ratkeava asetetaan ovat ratkeava.

Pidä ongelmia

Pysäyttää ongelma kuvataan kysymys siitä, onko algoritmi päättyy sisääntulon kanssa . Alan Turing osoitti tämän kysymyksen ratkaisemattomuuden. Muodollisemmin pito-ongelma on algoritmi- ja tuloparien ominaisuus , jonka algoritmi lopettaa tulolle , toisin sanoen, se laskee vain äärimmäisen pitkän. Tasainen pito-ongelma, nimittäin algoritmien ominaisuus lopullisesti pitää kiinni jokaisessa syötteessä, on myös ratkaisematon.

Monien heikompien laskentamallien, kuten lineaarisesti rajoitettujen Turingin koneiden , pysäytysongelma voidaan kuitenkin päättää.

Lausuntalogiikan pätevyys

Lausekkeen pätevyys on päätettävissä. Täydennys tähän tunnetaan, propositio-logiikan tyydyttävyysongelma . Yksi päätöksentekoprosessi on totuustaulukko- menetelmä .

Voimassa predikaattilogiikassa

Predikaatti-logiikan erityinen päätösongelma esitti David Hilbert vuonna 1928 (katso Hilbert-ohjelma ). Alan Turing ja Alonzo Church löysi ongelman vuonna 1936 olevan ratkaisematon (ks tilalla ongelma ).

Päätösongelmaa ei ole ratkaistu yleisen predikaattilogiikan osalta, vaan vain predikaattilogiikan osa-alueiden, kuten predikaattilogiikan, jossa on yksinumeroiset ensimmäisen kertaluvun predikaatit.

Diophantine-yhtälöiden ratkaisu

Polynomiyhtälöä kutsutaan Diophantineiksi, jos kaikki kertoimet ovat kokonaislukuja ja haetaan vain kokonaislukuratkaisuja. Omaisuutta diofantoksen yhtälö on ratkaisu ( Hilbertin kymmenes ongelma ) on ratkeamaton. Ratkeavuutta on lineaarinen Diophantine yhtälöt, toisaalta, on ratkeava.

Postin kirjeenvaihto-ongelma

Lopullista luetteloa ei-tyhjien sanaparien äärellisestä aakkosesta kutsutaan ongelmatapaukseksi. Yksi ratkaisu ongelmaan on ei-tyhjä, rajallinen numerosarja sanapareille luettelossa, joten sanaparien ensimmäiset komponentit, kun ne yhdistetään, johtavat samaan sanaan kuin sanaparien toiset komponentit.

Esimerkki: on ratkaisu, koska se pätee . ${\ displaystyle \ vasen (a, aba \ oikea), (ab, bb), (baa, aa)}$ ${\ displaystyle \ vasen (1,3,2,3 \ oikea)}$ ${\ displaystyle a \ cdot baa \ cdot ab \ cdot baa = abaaabbaa = aba \ cdot aa \ cdot bb \ cdot aa}$

Postsche vastaavuus ongelma , että on omaisuutta ongelma tapauksissa on ratkaisu, joka on undecidable.

fysiikka

Toby Cubittin, David Perez-Garcian ja Michael Wolfin mukaan seuraava kvanttimekaanisen monirunkoisen teorian ongelma on ratkaisematon. Annetaan kvanttimekaanisen monirunkoisen ongelman Hamilton-funktio. Onko spektrillä aukko ensimmäisestä viritetystä tilasta perustilaan vai ei? Kirjoittajat rakensivat nimenomaisesti kvantti spin -järjestelmien perheen kaksiulotteiseen ristikkoon, jolla on käännös-invariantti lähimmän naapurin vuorovaikutus, jolle kysymys spektrivälistä on ratkaisematon. He yhdistivät Hamilton-operaattoreiden monimutkaisuusteorian aperiodisen laatoituksen tekniikoihin ja muuntivat ongelman Turingin koneen pito-ongelmaksi. Myös muut järjestelmän pienenergiset ominaisuudet ovat ratkaisemattomia.

Liittyvät termit

Päätettäviä sarjoja yleisempi luokka ovat rekursiivisesti lueteltavat tai puolipäätettävät joukot , joissa ainoa kyllä-vaatimus on, että laskennan tulisi pysähtyä rajallisessa ajassa. Jos sekä joukko että sen komplementti ovat puolipäätettäviä, niin joukko on ratkaistavissa. Pysäytysongelma on osittain ratkaistavissa, koska vastaus "kyllä" voidaan antaa aina ajamalla ohjelmaa. Pidätysongelman täydennys ei kuitenkaan ole puolivalittavissa.

Katso myös

kirjallisuus

Lothar Czayka : Muodollinen logiikka ja tieteenfilosofia. Johdanto taloustieteilijöille. Oldenbourg, München ja muut 1991, ISBN 3-486-20987-6 , s. 45 ja sitä seuraavat.
Willard Van Orman Quine : Logiikan periaatteet. 8. painos. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4 , s. 142 s. ( Suhrkamp-Taschenbuch Wissenschaft 65), yksityiskohtaisesti.
Paul Hoyningen-Huene : Muodollinen logiikka. Filosofinen johdanto. Reclam, Stuttgart 1998, ISBN 3-15-009692-8 , s. 226 ja sitä seuraavaa ( Reclam's Universal Library 9692)
Hartley Rogers: Rekursiivisten toimintojen teoria ja tehokas laskettavuus . McGraw-Hill, 1967.
Uwe Schöning : Tietojenkäsittelyteoria - pähkinänkuoressa . 4. painos. Spectrum, 2000, ISBN 3-8274-1099-1 , s. 122 ff .

Yksittäiset todisteet

↑ Arnim Regenbogen, Uwe Meyer (Toim.): Sanakirja filosofisista termeistä. Erikoispainos. Meiner, Hampuri 2006, ISBN 3-7873-1761-9 , " päätettävä ".
Hil David Hilbert , W.Akkermann : Teoreettisen logiikan perusteet. 6. painos. Springer, Berliini et ai. 1972, ISBN 0-387-05843-5 , s. 119 ( Matemaattisten tieteiden perusopetukset 27).
↑ Alfred Tarski : Johdatus matemaattiseen logiikkaan. Viides painos, laajennettu sisällyttämään artikkeli "Totuus ja todisteet". Vandenhoeck & Ruprecht, Göttingen 1977, ISBN 3-525-40540-5 , s.145 ( Moderni matematiikka alkeiskuvauksessa 5).
↑ Patrick Brandt, Rolf-Albert Dietrich, Georg Schön: Kielitiede. Yhteinen ketju saksan kielen opiskeluun. 2. tarkistettu ja päivitetty painos. Böhlau, Köln ja muut 2006, ISBN 3-412-00606-8 , s. 14 ( UTB 8331).
↑ kopio on löydetty Achim Clausing klo Institute for Computer Science Westfalenin Wilhelms yliopistossa vuonna Münster ( Westfälische Nachrichten . 28 tammikuu 2013: jalanjäljillä edelläkävijä: Alkuperäinen vedokset tietojenkäsittelytieteessä Alan Turing ovat vuonna Münster yliopiston kirjasto ; verkossa ).
Bert Hilbert / Ackermann: Perusominaisuudet. 6. painos. (1972), s. 119.
↑ Willard Van Orman Quine : Logiikan periaatteet. 8. painos. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4 , s.247 .
^ Lothar Czayka: Muodollinen logiikka ja tieteenfilosofia. Johdanto taloustieteilijöille. Oldenbourg, München ja muut 1991, ISBN 3-486-20987-6 , s.45 .
↑ Cubitt, Perez-Garcia, Wolf, Spektrivälin undecidability, Nature, Volume 528, 2015, s.207 , Arxiv Preprint

[1] Arnim Regenbogen, Uwe Meyer (Toim.): Sanakirja filosofisista termeistä. Erikoispainos. Meiner, Hampuri 2006, ISBN 3-7873-1761-9 , " päätettävä ".

[2] Hil David Hilbert , W.Akkermann : Teoreettisen logiikan perusteet. 6. painos. Springer, Berliini et ai. 1972, ISBN 0-387-05843-5 , s. 119 ( Matemaattisten tieteiden perusopetukset 27).

[3] Alfred Tarski : Johdatus matemaattiseen logiikkaan. Viides painos, laajennettu sisällyttämään artikkeli "Totuus ja todisteet". Vandenhoeck & Ruprecht, Göttingen 1977, ISBN 3-525-40540-5 , s.145 ( Moderni matematiikka alkeiskuvauksessa 5).

[4] Patrick Brandt, Rolf-Albert Dietrich, Georg Schön: Kielitiede. Yhteinen ketju saksan kielen opiskeluun. 2. tarkistettu ja päivitetty painos. Böhlau, Köln ja muut 2006, ISBN 3-412-00606-8 , s. 14 ( UTB 8331).

[5] öydetty Achim Clausing klo Institute for Computer Science Westfalenin Wilhelms yliopistossa vuonna Münster ( Westfälische Nachrichten . 28 tammikuu 2013: jalanjäljillä edelläkävijä: Alkuperäinen vedokset tietojenkäsittelytieteessä Alan Turing ovat vuonna Münster yliopiston kirjasto ; verkossa ).

[6] Bert Hilbert / Ackermann: Perusominaisuudet. 6. painos. (1972), s. 119.

[7] Willard Van Orman Quine : Logiikan periaatteet. 8. painos. Suhrkamp, Frankfurt am Main 1993, ISBN 3-518-27665-4 , s.247 .

[8] Lothar Czayka: Muodollinen logiikka ja tieteenfilosofia. Johdanto taloustieteilijöille. Oldenbourg, München ja muut 1991, ISBN 3-486-20987-6 , s.45 .

[9] Cubitt, Perez-Garcia, Wolf, Spektrivälin undecidability, Nature, Volume 528, 2015, s.207 , Arxiv Preprint

Languages