Church-Turingin teesi viittaa tehokkaan, systemaattisen tai mekaanisen menetelmän käsitteeseen logiikassa, matematiikassa ja tietojenkäsittelytieteessä. Se on muotoiltu kuvaukseksi intuitiivisesta laskettavuuden käsitteestä ja yleisten rekursiivisten funktioiden yhteydessä sitä kutsutaan useammin Churchin opinnäytetyöksi. Se viittaa myös tietokoneella laskettavien funktioiden teoriaan. Väitöskirja ilmestyi 1930-luvulla, jolloin itse tietokoneita ei vielä ollut olemassa. Se nimettiin myöhemmin amerikkalaisen matemaatikon Alonso Churchin ja hänen brittiläisen kollegansa Alan Turingin mukaan.
Menetelmän tehokkuus tuloksen saavuttamiseksi
Ensimmäinen modernia tietokonetta muistuttava laite oli Bombie, englantilaisen matemaatikon Alan Turingin luoma kone. Sitä käytettiin saksalaisten viestien tulkitsemiseen toisen maailmansodan aikana. Mutta väitöskirjaansa ja algoritmin käsitteen formalisointiin hän käytti abstrakteja koneita, joita myöhemmin kutsuttiin Turingin koneiksi. Opinnäytetyö esitteleekiinnostavat sekä matemaatikot että ohjelmoijat, sillä tämä idea inspiroi ensimmäisten tietokoneiden luojia.
Laskettavuusteoriassa Church-Turingin teesi tunnetaan myös arvauksena laskettavien funktioiden luonteesta. Siinä todetaan, että jokaiselle luonnollisten lukujen algoritmisesti laskettavalle funktiolle on olemassa Turingin kone, joka pystyy laskemaan sen. Tai toisin sanoen, sille on olemassa sopiva algoritmi. Tunnettu esimerkki tämän menetelmän tehokkuudesta on totuustaulukkotesti tautologian testaamiseen.
Tapaa saavuttaa haluttu tulos kutsutaan "tehokkaaksi", "systeemiseksi" tai "mekaaniseksi", jos:
- Menetelmä määritellään äärellisenä määränä tarkkoja ohjeita, jokainen käsky ilmaistaan äärellisellä määrällä merkkejä.
- Se toimii ilman virheitä, tuottaa halutun tuloksen tietyssä määrässä vaiheita.
- Ihminen voi suorittaa menetelmän ilman apua millään muulla välineellä kuin paperilla ja kynällä
- Se ei vaadi toiminnon suorittaj alta ymmärrystä, intuitiota tai kekseliäisyyttä
Aiemmin matematiikassa epävirallista termiä "tehokkaasti laskettava" käytettiin viittaamaan funktioihin, jotka voidaan laskea kynällä ja paperilla. Mutta itse käsitys algoritmisesta laskettavuudesta oli intuitiivisempi kuin mikään konkreettinen. Nyt sille oli ominaista luonnollisella argumentilla varustettu funktio, jolle on olemassa laskenta-algoritmi. Yksi Alan Turingin saavutuksista olimuodollisesti tarkan predikaatin esitys, jonka avulla voitaisiin korvata epämuodollinen, jos menetelmän tehokkuusehtoa käytetään. Kirkko teki saman löydön.
Rekursiivisten funktioiden peruskäsitteet
Turingin predikaattien muutos näytti ensi silmäyksellä erilaiselta kuin hänen kollegansa ehdottama. Mutta seurauksena ne osoittautuivat vastaaviksi siinä mielessä, että jokainen niistä valitsee saman joukon matemaattisia funktioita. Church-Turingin teesi on väite, että tämä joukko sisältää kaikki funktiot, joiden arvot voidaan saada tehokkuusehdot täyttävällä menetelmällä. Näiden kahden löydön välillä oli toinenkin ero. Church piti vain esimerkkejä positiivisista kokonaisluvuista, kun taas Turing kuvaili työtään laskevan funktioiden kattavan integraali- tai reaalimuuttujan kanssa.
Yleiset rekursiiviset funktiot
Kirkon alkuperäinen muotoilu sanoo, että laskelma voidaan tehdä käyttämällä λ-laskentaa. Tämä vastaa yleisten rekursiivisten funktioiden käyttöä. Church-Turingin opinnäytetyö kattaa enemmän laskentamuotoja kuin alun perin uskottiin. Esimerkiksi liittyen solukkoautomaatteihin, kombinaattoreihin, rekisteröintikoneisiin ja korvausjärjestelmiin. Vuonna 1933 matemaatikot Kurt Gödel ja Jacques Herbrand loivat muodollisen määritelmän luokalle, jota kutsutaan yleisiksi rekursiivisiksi funktioiksi. Se käyttää funktioita, joissa useampi kuin yksi argumentti on mahdollinen.
Menetelmän luominenλ-laskenta
Vuonna 1936 Alonso Church loi määritysmenetelmän, jota kutsutaan λ-laskemiseksi. Hänet yhdistettiin luonnollisiin lukuihin. Tiedemies määritti niiden koodauksen λ-laskennassa. Tämän seurauksena niitä kutsutaan kirkon numeroiksi. Luonnollisiin lukuihin perustuvaa funktiota kutsuttiin λ-laskettavaksi. Oli toinenkin määritelmä. Churchin opinnäytetyön funktiota kutsutaan λ-laskettavaksi kahdella ehdolla. Ensimmäinen kuulosti tältä: jos se laskettiin kirkon elementeistä, ja toinen ehto oli mahdollisuus edustaa λ-laskennan jäsen.
Myös vuonna 1936, ennen kuin hän tutki kollegansa töitä, Turing loi teoreettisen mallin abstrakteille koneille, jotka nyt on nimetty hänen mukaansa. He pystyivät suorittamaan laskelmia manipuloimalla nauhan merkkejä. Tämä koskee myös muita teoreettisen tietojenkäsittelytieteen matemaattisia toimintoja, kuten kvanttitodennäköisyyslaskentaa. Churchin opinnäytetyön funktio perustettiin vasta myöhemmin Turingin koneella. Aluksi he luottivat λ-laskentaan.
Funktion laskettavuus
Kun luonnolliset luvut on koodattu asianmukaisesti merkkijonoiksi, luonnollisten lukujen funktion sanotaan olevan Turing-laskettavissa, jos abstrakti kone on löytänyt tarvittavan algoritmin ja tulostanut tämän funktion nauhalle. Tällaista laitetta, jota ei ollut 1930-luvulla, pidettäisiin tulevaisuudessa tietokoneena. Abstrakti Turingin kone ja Churchin teesi ennustivat kehityksen aikakauttatietokonelaitteet. Osoitettiin, että molempien tiedemiesten muodollisesti määrittelemät funktioluokat ovat samat. Tämän seurauksena molemmat lausunnot yhdistettiin yhdeksi. Laskennalliset funktiot ja Churchin opinnäytetyö vaikuttivat vahvasti myös laskettavuuden käsitteeseen. Niistä tuli myös tärkeä työkalu matemaattiselle logiikalle ja todistusteorialle.
Menetelmän perustelut ja ongelmat
Tilötyöstä on ristiriitaisia näkemyksiä. Churchin ja Turingin vuonna 1936 esittämälle "työhypoteesille" kerättiin lukuisia todisteita. Mutta kaikki tunnetut menetelmät tai toiminnot uusien tehokkaasti laskettavien funktioiden löytämiseksi annetuista yhdistettiin koneiden rakentamisen menetelmiin, joita ei silloin ollut olemassa. Church-Turingin teesin todistamiseksi lähdetään siitä tosiasiasta, että jokainen realistinen laskentamalli on ekvivalentti.
Erilaisten analyysien vuoksi tätä pidetään yleensä erityisen vahvana todisteena. Kaikki yritykset määritellä tarkemmin intuitiivinen käsite tehokkaasti laskettavasta funktiosta osoittautuivat vastaaviksi. Jokainen ehdotettu analyysi on osoittanut erottavan saman luokan funktioita, nimittäin ne, jotka ovat laskettavissa Turingin koneilla. Jotkut laskennalliset mallit osoittautuivat kuitenkin tehokkaammiksi ajan ja muistin käytön suhteen eri tehtäviin. Myöhemmin todettiin, että rekursiivisten funktioiden peruskäsitteet ja Churchin teesi ovat melko hypoteettisia.
Thesis M
On tärkeää tehdä ero Turingin teesin ja väitteen välillä, että kaikki, mitä laskentalaite voi laskea, voidaan laskea sen koneella. Toisella vaihtoehdolla on oma määritelmänsä. Gandhi kutsuu toista virkettä "Thesis M". Se menee näin: "Mitä tahansa laite voi laskea, sen voi laskea Turingin kone." Opinnäytetyön suppeassa merkityksessä se on empiirinen väite, jonka totuusarvoa ei tunneta. Turingin teesi ja "Thesis M" sekoitetaan toisinaan. Toinen versio on pääosin virheellinen. On kuvattu useita ehdollisia koneita, jotka voivat laskea funktioita, jotka eivät ole Turingin laskettavissa. On tärkeää huomata, että ensimmäinen opinnäytetyö ei sisällä toista, vaan on yhdenmukainen sen valheellisuuden kanssa.
Tipin käänteinen implikaatio
Lasketettavuusteoriassa Churchin väitöskirjaa käytetään laskettavuuden käsitteen kuvauksena yleisten rekursiivisten funktioiden luokassa. Amerikkalainen Stephen Kleene antoi yleisemmän muotoilun. Hän kutsui osittain rekursiivisiksi kaikkia algoritmeilla laskettavia osittaisfunktioita.
Käänteinen implikaatio kutsutaan yleisesti kirkon käänteiseksi teesiksi. Se johtuu siitä, että jokainen positiivisten kokonaislukujen rekursiivinen funktio arvioidaan tehokkaasti. Suppeassa merkityksessä opinnäytetyö yksinkertaisesti merkitsee tällaista mahdollisuutta. Ja laajemmassa merkityksessä se irtaantuu kysymyksestä, voiko tämä ehdollinen kone olla siinä.
Kvanttitietokoneet
Laskettavien funktioiden käsitteistä ja Churchin opinnäytetyöstä tuli tärkeä löytö matematiikan, koneteorian ja monien muiden tieteiden kann alta. Mutta tekniikka on muuttunut paljon ja paranee edelleen. Oletetaan, että kvanttitietokoneet pystyvät suorittamaan monia yleisiä tehtäviä lyhyemmässä ajassa kuin nykyaikaiset tietokoneet. Mutta kysymyksiä on jäljellä, kuten pysäytysongelma. Kvanttitietokone ei voi vastata siihen. Eikä Church-Turingin teesin mukaan myöskään mitään muuta laskentalaitetta.
