Church-Turingo tezė nurodo veiksmingo, sistemingo arba mechaninio metodo sąvoką logikoje, matematikoje ir kompiuterių moksle. Jis suformuluotas kaip intuityvios apskaičiavimo sampratos aprašymas ir, kalbant apie bendrąsias rekursines funkcijas, dažniau vadinamas Churcho teze. Tai taip pat reiškia kompiuterių skaičiuojamų funkcijų teoriją. Disertacija pasirodė praėjusio amžiaus ketvirtajame dešimtmetyje, kai pačių kompiuterių dar nebuvo. Vėliau jis buvo pavadintas amerikiečių matematiko Alonso Church ir jo kolegos britų Alano Turingo vardu.
Metodo efektyvumas norint pasiekti rezultatą
Pirmasis įrenginys, panašus į šiuolaikinį kompiuterį, buvo Bombie – mašina, kurią sukūrė anglų matematikas Alanas Turingas. Jis buvo naudojamas vokiečių žinutėms iššifruoti Antrojo pasaulinio karo metais. Tačiau savo disertacijai ir algoritmo sampratos formalizavimui jis panaudojo abstrakčias mašinas, vėliau pavadintas Tiuringo mašinomis. Pristatomas baigiamasis darbasir matematikai, ir programuotojai, nes ši idėja įkvėpė pirmųjų kompiuterių kūrėjus.
Apskaičiuojamumo teorijoje Church-Turingo tezė taip pat žinoma kaip spėjimas apie apskaičiuojamų funkcijų prigimtį. Jame teigiama, kad bet kuriai algoritmiškai apskaičiuojamai natūraliųjų skaičių funkcijai yra Tiuringo mašina, galinti ją apskaičiuoti. Arba, kitaip tariant, yra tam tinkamas algoritmas. Gerai žinomas šio metodo veiksmingumo pavyzdys yra tiesos lentelės testas tautologijai tirti.
Būdas pasiekti bet kokį norimą rezultatą vadinamas „veiksmingu“, „sistemingu“arba „mechaniniu“, jei:
- Metodas nurodomas baigtiniu tikslių instrukcijų skaičiumi, kiekviena instrukcija išreiškiama naudojant baigtinį simbolių skaičių.
- Jis veiks be klaidų, duos norimą rezultatą atlikus tam tikrą žingsnių skaičių.
- Šį metodą gali atlikti žmogus be pagalbos, naudodamas bet kokią kitą įrangą, išskyrus popierių ir pieštuką
- Iš veiksmą atliekančio asmens nereikia supratimo, intuicijos ar išradingumo
Anksčiau matematikoje neoficialus terminas „efektyviai apskaičiuojamas“buvo naudojamas funkcijoms, kurias galima apskaičiuoti pieštuku ir popieriumi, nurodyti. Tačiau pati algoritminio apskaičiavimo samprata buvo labiau intuityvi nei bet kas konkretus. Dabar jis buvo apibūdintas funkcija su natūraliu argumentu, kuriai yra skaičiavimo algoritmas. Vienas iš Alano Turingo laimėjimų buvoformaliai tikslaus predikato atvaizdavimas, kurio pagalba būtų galima pakeisti neformalųjį, jei naudojama metodo efektyvumo sąlyga. Bažnyčia padarė tą patį atradimą.
Pagrindinės rekursinių funkcijų sąvokos
Turingo predikatų pasikeitimas iš pirmo žvilgsnio atrodė kitaip nei jo kolegos pasiūlytas. Tačiau dėl to jie pasirodė lygiaverčiai ta prasme, kad kiekvienas iš jų pasirenka tą patį matematinių funkcijų rinkinį. Church-Turingo tezė teigia, kad šiame rinkinyje yra kiekviena funkcija, kurios reikšmes galima gauti metodu, kuris tenkina efektyvumo sąlygas. Tarp dviejų atradimų buvo dar vienas skirtumas. Bažnyčia laikė tik teigiamų sveikųjų skaičių pavyzdžius, o Turingas apibūdino savo darbą kaip apimantį skaičiuojamas funkcijas su integraliu arba realiu kintamuoju.
Bendrosios rekursinės funkcijos
Bažnyčios pradinėje formuluotėje teigiama, kad skaičiavimus galima atlikti naudojant λ skaičiavimą. Tai prilygsta bendrųjų rekursinių funkcijų naudojimui. Church-Turingo disertacija apima daugiau skaičiavimo rūšių, nei manyta iš pradžių. Pavyzdžiui, susiję su korinio ryšio automatais, kombinatoriais, registravimo mašinomis ir pakeitimo sistemomis. 1933 m. matematikai Kurtas Gödelis ir Jacques'as Herbrandas sukūrė formalų klasės, vadinamos bendrosiomis rekursinėmis funkcijomis, apibrėžimą. Jame naudojamos funkcijos, kuriose galimas daugiau nei vienas argumentas.
Metodo kūrimasλ-skaičiavimas
1936 m. Alonso Church sukūrė nustatymo metodą, vadinamą λ skaičiavimu. Jis buvo siejamas su natūraliaisiais skaičiais. λ skaičiavime mokslininkas nustatė jų kodavimą. Dėl to jie vadinami Bažnyčios numeriais. Natūraliaisiais skaičiais pagrįsta funkcija buvo vadinama λ-apskaičiuojama. Buvo dar vienas apibrėžimas. Funkcija iš Churcho tezės vadinama λ-apskaičiuojama dviem sąlygomis. Pirmasis skambėjo taip: jei jis buvo apskaičiuotas pagal bažnyčios elementus, o antroji sąlyga buvo galimybė būti atstovaujamam λ skaičiavimo nariu.
Taip pat 1936 m., prieš studijuodamas savo kolegos darbus, Turingas sukūrė teorinį modelį abstrakčioms mašinoms, dabar pavadintoms jo vardu. Jie galėjo atlikti skaičiavimus manipuliuodami juostoje esančiais simboliais. Tai taip pat taikoma kitai matematinei veiklai, randamai teoriniame kompiuterių moksle, pavyzdžiui, kvantiniam tikimybiniam skaičiavimui. Churcho disertacijos funkcija tik vėliau buvo pagrįsta Tiuringo mašina. Iš pradžių jie rėmėsi λ skaičiavimu.
Funkcijų apskaičiuojamumas
Kai natūralieji skaičiai yra tinkamai užkoduoti kaip simbolių sekos, natūraliųjų skaičių funkcija yra apskaičiuojama pagal Tiuringo metodą, jei abstrakčioji mašina rado reikiamą algoritmą ir atspausdino šią funkciją juostoje. Toks įrenginys, kurio 1930-aisiais nebuvo, ateityje bus laikomas kompiuteriu. Abstrakti Tiuringo mašina ir Churcho tezė skelbė vystymosi erąskaičiavimo prietaisai. Įrodyta, kad abiejų mokslininkų formaliai apibrėžtos funkcijų klasės sutampa. Todėl abu teiginiai buvo sujungti į vieną. Skaičiavimo funkcijos ir Churcho disertacija taip pat turėjo didelę įtaką apskaičiuojamumo sampratai. Jie taip pat tapo svarbia matematinės logikos ir įrodymų teorijos priemone.
Metodo pagrindimas ir problemos
Dėl disertacijos yra prieštaringų požiūrių. Buvo surinkta daugybė įrodymų, patvirtinančių „darbinę hipotezę“, kurią Church ir Turing pasiūlė 1936 m. Tačiau visi žinomi metodai ar operacijos, leidžiančios atrasti naujas efektyviai apskaičiuojamas funkcijas iš pateiktų, buvo susietos su mašinų kūrimo metodais, kurių tada dar nebuvo. Norint įrodyti Church-Turingo tezę, reikia pradėti nuo to, kad kiekvienas realus skaičiavimo modelis yra lygiavertis.
Dėl skirtingų analizių įvairovės tai paprastai laikoma ypač tvirtu įrodymu. Visi bandymai tiksliau apibrėžti intuityvią efektyviai apskaičiuojamos funkcijos sąvoką pasirodė lygiaverčiai. Įrodyta, kad kiekviena pasiūlyta analizė išskiria tą pačią funkcijų klasę, būtent tas, kurias apskaičiuoja Turingo mašinos. Tačiau kai kurie skaičiavimo modeliai pasirodė esąs veiksmingesni laiko ir atminties naudojimo įvairioms užduotims požiūriu. Vėliau buvo pastebėta, kad pagrindinės rekursinių funkcijų sąvokos ir Churcho tezės yra gana hipotetinės.
„Dezė M“
Svarbu atskirti Turingo tezę ir teiginį, kad viską, ką gali apskaičiuoti skaičiavimo įrenginys, gali apskaičiuoti jo mašina. Antrasis variantas turi savo apibrėžimą. Antrąjį sakinį Gandis vadina „Teze M“. Tai skamba taip: „Viską, ką gali apskaičiuoti įrenginys, gali apskaičiuoti Tiuringo mašina“. Siaurąja disertacijos prasme tai yra empirinis teiginys, kurio tiesos vertė nežinoma. Turingo tezė ir „M tezė“kartais painiojamos. Antroji versija iš esmės neteisinga. Buvo aprašytos įvairios sąlyginės mašinos, galinčios apskaičiuoti funkcijas, kurios nėra apskaičiuojamos pagal Turingą. Svarbu pažymėti, kad pirmoji tezė neapima antrosios, bet atitinka jos klaidingumą.
Atvirkštinė disertacijos reikšmė
Apskaičiuojamumo teorijoje Churcho tezė naudojama kaip apskaičiuojamumo sąvokos aprašymas pagal bendrųjų rekursinių funkcijų klasę. Amerikietis Stephenas Kleene'as pateikė bendresnę formuluotę. Jis pavadino dalinai rekursyviomis visas dalines funkcijas, kurias galima apskaičiuoti naudojant algoritmus.
Atvirkštinė implikacija paprastai vadinama atvirkštine Bažnyčios teze. Tai slypi tame, kad kiekviena teigiamų sveikųjų skaičių rekursinė funkcija yra efektyviai įvertinama. Siaurąja prasme tezė tiesiog reiškia tokią galimybę. Ir platesne prasme jis abstrahuojasi nuo klausimo, ar ši sąlyginė mašina gali joje egzistuoti.
Kvantiniai kompiuteriai
Apskaičiuojamųjų funkcijų sąvokos ir Churcho tezė tapo svarbiu matematikos, mašinų teorijos ir daugelio kitų mokslų atradimu. Tačiau technologijos labai pasikeitė ir toliau tobulėja. Daroma prielaida, kad kvantiniai kompiuteriai gali atlikti daug įprastų užduočių per trumpesnį laiką nei šiuolaikiniai. Tačiau lieka klausimų, pavyzdžiui, sustabdymo problema. Kvantinis kompiuteris negali į tai atsakyti. Ir pagal Church-Turing tezę, joks kitas skaičiavimo įrenginys.
