Lasketettavuuden teoria

Lasketettavuuden teoria , joka tunnetaan myös nimellä rekursiivisten funktioiden teoria, on modernin matematiikan haara, joka sijaitsee matemaattisen logiikan , algoritmien teorian ja tietojenkäsittelytieteen risteyksessä , joka syntyi laskettavuuden ja ei-käsitteiden tutkimisen tuloksena. - laskettavuus. Aluksi teoria oli omistettu laskettaville ja ei-laskettavissa oleville funktioille ja eri laskentamallien vertailulle . Nyt laskettavuuden teorian tutkimuskenttä on laajentunut - laskettavuuden käsitteen uusia määritelmiä ilmaantuu ja matemaattiseen logiikkaan on tulossa fuusio , jossa puhutaan laskettavuuden ja ei-laskettavuuden sijasta todentettavuudesta ja todistamattomuudesta (pääteltävissä ja ei-todistettavuudesta). -johdettavuus) minkä tahansa teorian puitteissa.

Lasketettavuuden teoria on peräisin Alan Turingin ( 1936 ) teoksesta "On Computable Numbers, With An Application to Entscheidungsproblem", jossa hän esitteli abstraktin tietokoneen käsitteen, joka myöhemmin sai nimensä, ja osoitti peruslauseen. sen pysäyttämisen ongelman ratkaisemattomuus . Gödelin kuuluisa epätäydellisyyslause ( 1931 ) todistettiin primitiivisillä rekursiivisilla funktioilla , joiden luokkaa Gödel laajensi vuonna 1934 yleisten rekursiivisten funktioiden luokkaan . Gödelin kehittämä formalismi osoittautui vastaavaksi Turingin (ja monien muiden) kanssa. Yhdessä Church-Turingin teesin kanssa tämä tosiasia osoitti selkeästi uuden teorian sisällön, ja nyt nämä määritelmät hyväksytään yleisesti algoritmisesti laskettavien funktioiden muodolliseksi analogiksi.

Gödelin laskennallisten funktioiden määritelmä oli luonteeltaan syntaktinen, ja vain tämän luokan yhteensopivuuden toteaminen yleisten rekursiivisten funktioiden luokan kanssa (yhdessä Churchin teesin muotoilun ja "hyväksynnän" kanssa) osoitti epätäydellisyyslauseen todellisen merkityksen.Ershov, Juri Leonidovitš

Katso myös

• Ricen lause
• Lopeta ongelma

• Kurt Gödel
• Alan Turing
• Stephen Kleene
• Alonzon kirkko
• Emil Post

Kirjallisuus

• Boolos J., Jeffrey R. Lasketettavuus ja logiikka. - M .: Mir, 1994. - 396 s.
• Ershov Yu.L. Numerointiteoria. - M .: Nauka, 1977. - 416 s.
• Cutland N. Lasketettavuus . Johdatus rekursiivisten funktioiden teoriaan - M. : Mir, 1986. - 256 s.
• Kleene. Johdatus metamatematiikkaan. - M . : Ulkomaisen kirjallisuuden kustantamo, 1957. - 526 s.
• Maltsev A.I. Algoritmit ja rekursiiviset funktiot. - M .: Nauka, 1965. - 392 s.
• Manin Yu.I. Laskettavissa ja ei-laskettavissa. - M . : Neuvostoliiton radio, 1980. - 128 s.
• Minsky M. Laskut ja automaatit. - M .: Mir, 1971. - 366 s.
• Hodgers H. Rekursiivisten funktioiden teoria ja tehokas laskettavuus. - M .: Mir, 1972. - 624 s.
• Barweis J. Matemaattisen logiikan hakuteos neljässä osassa. Osa III. Rekursioteoria .. - M . : Nauka, 1982. - 360 s.
• Uspensky V.A. Luennot laskettavissa olevista funktioista. - M .: Fizmatgiz, 1960. - 492 s.
• Uspensky V.A., Semenov L.A. Algoritmien teoria: tärkeimmät löydöt ja sovellukset. - M .: Nauka, 1987.
• Shenfield J. Päättämättömyyden asteet. - M .: Nauka, 1977. - 192 s.

Linkit