Kiriku-Turingi tees viitab tõhusa, süstemaatilise või mehaanilise meetodi kontseptsioonile loogikas, matemaatikas ja arvutiteaduses. See on sõnastatud arvutatavuse intuitiivse kontseptsiooni kirjeldusena ja seoses üldiste rekursiivsete funktsioonidega nimetatakse seda sagedamini Churchi teesiks. See viitab ka arvutiga arvutatavate funktsioonide teooriale. Lõputöö ilmus 1930. aastatel, kui arvuteid endid veel ei eksisteerinud. Hiljem sai see nime Ameerika matemaatiku Alonso Churchi ja tema Briti kolleegi Alan Turingi järgi.
Meetodi tõhusus tulemuse saavutamiseks
Esimene seade, mis meenutas kaasaegset arvutit, oli inglise matemaatiku Alan Turingi loodud masin Bombie. Seda kasutati Saksa sõnumite dešifreerimiseks Teise maailmasõja ajal. Kuid oma lõputööks ja algoritmi kontseptsiooni vormistamiseks kasutas ta abstraktseid masinaid, mida hiljem nimetati Turingi masinateks. Lõputöö esitlebhuvi nii matemaatikute kui ka programmeerijate vastu, kuna see idee inspireeris esimeste arvutite loojaid.
Arvutavuse teoorias on Church-Turingi teesi tuntud ka kui oletust arvutatavate funktsioonide olemuse kohta. Selles öeldakse, et iga naturaalarvude algoritmiliselt arvutatava funktsiooni jaoks on Turingi masin, mis on võimeline seda arvutama. Või teisisõnu on selleks sobiv algoritm. Tuntud näide selle meetodi tõhususest on tautoloogia testimiseks mõeldud tõetabeli test.
Viisi soovitud tulemuse saavutamiseks nimetatakse "tõhusaks", "süstemaatiliseks" või "mehaaniliseks", kui:
- Meetod on määratletud piiratud arvu täpsete käskude kaudu, iga käsklust väljendatakse piiratud arvu märkide abil.
- See töötab ilma vigadeta, annab soovitud tulemuse teatud arvu etappidega.
- Meetodit saab läbi viia inimene ilma abita, kasutades muid seadmeid peale paberi ja pliiatsi
- See ei nõua toimingu sooritaj alt mõistmist, intuitsiooni ega leidlikkust
Varem matemaatikas kasutati mitteametlikku terminit "tõhus alt arvutatav" funktsioonide tähistamiseks, mida saab arvutada pliiatsi ja paberiga. Algoritmilise arvutatavuse mõiste oli aga intuitiivsem kui miski konkreetne. Nüüd iseloomustas seda loomuliku argumendiga funktsioon, mille jaoks on olemas arvutusalgoritm. Üks Alan Turingi saavutusi oliformaalselt täpse predikaadi esitus, mille abil oleks võimalik asendada mitteformaalne, kui kasutada meetodi efektiivsuse tingimust. Kirik tegi sama avastuse.
Rekursiivsete funktsioonide põhimõisted
Turingi predikaatide muutus tundus esmapilgul erinev tema kolleegi pakutust. Kuid selle tulemusena osutusid need samaväärseteks selles mõttes, et igaüks neist valib sama matemaatiliste funktsioonide komplekti. Church-Turingi väitekiri on väide, et see komplekt sisaldab kõiki funktsioone, mille väärtused on võimalik saada efektiivsustingimustele vastava meetodiga. Nende kahe avastuse vahel oli veel üks erinevus. See oli see, et Church käsitles ainult positiivsete täisarvude näiteid, samas kui Turing kirjeldas oma tööd kui integraal- või reaalmuutujaga arvutatavate funktsioonide katmist.
Levinud rekursiivsed funktsioonid
Churchi algses sõnastuses on kirjas, et arvutusi saab teha λ-arvutuse abil. See on samaväärne üldiste rekursiivsete funktsioonide kasutamisega. Church-Turingi väitekiri hõlmab rohkem arvutusliike, kui algselt arvati. Näiteks seotud mobiilsideautomaatide, kombinaatorite, registreerimismasinate ja asendussüsteemidega. 1933. aastal lõid matemaatikud Kurt Gödel ja Jacques Herbrand klassi ametliku määratluse, mida nimetatakse üldisteks rekursiivseteks funktsioonideks. See kasutab funktsioone, kus on võimalik rohkem kui üks argument.
Meetodi loomineλ-arvutus
1936. aastal lõi Alonso Church määramismeetodi, mida nimetatakse λ-arvutuseks. Teda seostati naturaalarvudega. λ-arvutuses määras teadlane nende kodeeringu. Seetõttu nimetatakse neid kirikunumbriteks. Naturaalarvudel põhinevat funktsiooni nimetati λ-arvutatavaks. Oli veel üks määratlus. Churchi väitekirja funktsiooni nimetatakse λ-arvutatavaks kahel tingimusel. Esimene kõlas nii: kui see arvutati kiriku elementide põhjal, ja teine tingimus oli võimalus, et teda esindab λ-arvutuse liige.
Ka 1936. aastal, enne kolleegi tööga tutvumist, lõi Turing teoreetilise mudeli abstraktsetele masinatele, mis on nüüdseks tema nime saanud. Nad said teha arvutusi, manipuleerides lindil olevaid tegelasi. See kehtib ka muude teoreetilises arvutiteaduses leiduvate matemaatiliste tegevuste kohta, näiteks kvanttõenäosuslik arvutamine. Churchi väitekirja funktsiooni põhjendati alles hiljem Turingi masina abil. Algselt toetusid nad λ-arvutusele.
Funktsioonide arvutatavus
Kui naturaalarvud on asjakohaselt kodeeritud märgijadadena, siis öeldakse, et naturaalarvude funktsioon on Turingi järgi arvutatav, kui abstraktne masin leidis vajaliku algoritmi ja printis selle funktsiooni lindile. Sellist seadet, mida 1930. aastatel ei eksisteerinud, peetakse tulevikus arvutiks. Abstraktne Turingi masin ja Churchi tees kuulutasid arengu ajastutarvutusseadmed. Tõendati, et mõlema teadlase poolt formaalselt määratletud funktsioonide klassid langevad kokku. Seetõttu ühendati mõlemad väited üheks. Arvutusfunktsioonid ja Churchi tees avaldasid samuti tugevat mõju arvutatavuse mõistele. Neist sai ka oluline tööriist matemaatilise loogika ja tõestusteooria jaoks.
Meetodi põhjendus ja probleemid
Lõputöö kohta on vastakaid seisukohti. Churchi ja Turingi 1936. aastal välja pakutud "tööhüpoteesi" kohta koguti arvuk alt tõendeid. Kuid kõik teadaolevad meetodid või toimingud uute tõhus alt arvutatavate funktsioonide avastamiseks antud funktsioonidest olid seotud masinate ehitamise meetoditega, mida siis veel polnud. Church-Turingi teesi tõestamiseks tuleb lähtuda tõsiasjast, et iga realistlik arvutusmudel on samaväärne.
Erinevate analüüside mitmekesisuse tõttu peetakse seda üldiselt eriti tugevaks tõendiks. Kõik katsed tõhus alt arvutatava funktsiooni intuitiivset mõistet täpsem alt määratleda osutusid samaväärseteks. Iga välja pakutud analüüs on näidanud, et toob esile sama funktsioonide klassi, nimelt need, mida Turingi masinad arvutavad. Kuid mõned arvutusmudelid osutusid erinevate ülesannete jaoks aja ja mälukasutuse osas tõhusamaks. Hiljem märgiti, et rekursiivsete funktsioonide põhimõisted ja Churchi tees on pigem hüpoteetilised.
Lõputöö M
Oluline on teha vahet Turingi teesil ja väitel, et kõike, mida saab arvutada arvutusseade, saab arvutada selle masin. Teisel variandil on oma määratlus. Gandhi nimetab teist lauset "Thesis M". See kõlab nii: "Kõik, mida seade suudab arvutada, saab arvutada Turingi masin." Töö kitsamas tähenduses on see empiiriline propositsioon, mille tõeväärtus on teadmata. Turingi tees ja "M-tees" aetakse mõnikord segamini. Teine versioon on üldjoontes vale. Kirjeldatud on mitmesuguseid tingimuslikke masinaid, mis suudavad arvutada funktsioone, mis ei ole Turingi arvutatavad. Oluline on märkida, et esimene tees ei hõlma teist, vaid on kooskõlas selle väärusega.
Lõputöö pöördimplikatsioon
Arvutavuse teoorias kasutatakse Churchi teesi arvutatavuse mõiste kirjeldusena üldiste rekursiivsete funktsioonide klassi järgi. Ameeriklane Stephen Kleene andis üldisema sõnastuse. Ta nimetas osaliselt rekursiivseteks kõik osafunktsioonid, mida saab arvutada algoritmide abil.
Pöördimplikatsiooni nimetatakse tavaliselt Kiriku vastupidiseks teesiks. See seisneb selles, et iga positiivsete täisarvude rekursiivset funktsiooni hinnatakse tõhus alt. Kitsas tähenduses tähistab lõputöö lihts alt sellist võimalust. Ja laiemas mõttes abstraheerub see küsimusest, kas see tingimuslik masin saab selles eksisteerida.
Kvantarvutid
Arvutatavate funktsioonide kontseptsioonist ja Churchi teesist sai matemaatika, masinateooria ja paljude teiste teaduste jaoks oluline avastus. Kuid tehnoloogia on palju muutunud ja paraneb jätkuv alt. Eeldatakse, et kvantarvutid suudavad täita paljusid tavalisi ülesandeid lühema ajaga kui tänapäevased. Kuid küsimused jäävad, näiteks peatumisprobleem. Kvantarvuti ei suuda sellele vastata. Ja Church-Turingi teesi kohaselt pole ka ühtegi teist arvutusseadet.
