Čērča-Tjūringa tēze attiecas uz efektīvas, sistemātiskas vai mehāniskas metodes jēdzienu loģikā, matemātikā un datorzinātnēs. Tas ir formulēts kā intuitīvās aprēķinojamības jēdziena apraksts un saistībā ar vispārējām rekursīvajām funkcijām biežāk tiek saukts par Church's tēzi. Tas attiecas arī uz datoru skaitļojamo funkciju teoriju. Disertācija parādījās 20. gadsimta 30. gados, kad paši datori vēl nepastāvēja. Vēlāk to nosauca amerikāņu matemātiķa Alonso Čērča un viņa britu kolēģa Alana Tjūringa vārdā.
Metodes efektivitāte rezultāta sasniegšanai
Pirmā ierīce, kas atgādināja mūsdienu datoru, bija Bombie - mašīna, ko radīja angļu matemātiķis Alans Tjūrings. To izmantoja vācu vēstījumu atšifrēšanai Otrā pasaules kara laikā. Bet savai tēzei un algoritma jēdziena formalizēšanai viņš izmantoja abstraktās mašīnas, kuras vēlāk sauca par Tjūringa mašīnām. Diplomdarbu prezentācijasinteresi gan matemātiķiem, gan programmētājiem, jo šī ideja iedvesmoja pirmo datoru veidotājus.
Aprēķināmības teorijā Čērča-Tjūringa tēze ir pazīstama arī kā minējums par izskaitļojamo funkciju būtību. Tajā teikts, ka jebkurai algoritmiski izskaitļojamai naturālu skaitļu funkcijai ir Tjūringa mašīna, kas spēj to aprēķināt. Vai, citiem vārdiem sakot, ir tam piemērots algoritms. Labi zināms šīs metodes efektivitātes piemērs ir patiesības tabulas tests tautoloģijas pārbaudei.
Veids, kā sasniegt jebkuru vēlamo rezultātu, tiek saukts par "efektīvu", "sistemātisku" vai "mehānisku", ja:
- Metode ir norādīta ar noteiktu skaitu precīzu instrukciju, katra instrukcija tiek izteikta, izmantojot ierobežotu rakstzīmju skaitu.
- Tas darbosies bez kļūdām, sniegs vēlamo rezultātu noteiktā soļu skaitā.
- Šo metodi var veikt cilvēks bez palīdzības ar jebkuru aprīkojumu, izņemot papīru un zīmuli
- Tas neprasa izpratni, intuīciju vai atjautību no personas, kas veic darbību
Agrāk matemātikā neformāls termins "efektīvi aprēķināms" tika lietots, lai apzīmētu funkcijas, kuras var aprēķināt ar zīmuli un papīru. Bet pats algoritmiskās aprēķināšanas jēdziens bija intuitīvāks nekā jebkas konkrēts. Tagad to raksturoja funkcija ar dabisku argumentu, kurai ir aprēķina algoritms. Viens no Alana Tjūringa sasniegumiem bijaformāli precīza predikāta attēlojums, ar kura palīdzību būtu iespējams aizstāt neformālo, ja tiek izmantots metodes efektivitātes nosacījums. Baznīca izdarīja to pašu atklājumu.
Rekursīvo funkciju pamatjēdzieni
Tjūringa predikātu maiņa no pirmā acu uzmetiena izskatījās savādāka nekā viņa kolēģa piedāvātā. Bet rezultātā tie izrādījās līdzvērtīgi tādā nozīmē, ka katrs no tiem izvēlas vienu un to pašu matemātisko funkciju kopu. Čērča-Tjūringa tēze ir apgalvojums, ka šajā komplektā ir visas funkcijas, kuru vērtības var iegūt ar metodi, kas atbilst efektivitātes nosacījumiem. Starp abiem atklājumiem bija vēl viena atšķirība. Tā bija tā, ka Bačers uzskatīja tikai pozitīvu veselu skaitļu piemērus, savukārt Tjūrings savu darbu aprakstīja kā tādu, kas aptver izskaitļojamas funkcijas ar integrālu vai reālu mainīgo.
Biežākās rekursīvās funkcijas
Baznīcas sākotnējā formulējumā teikts, ka aprēķinu var veikt, izmantojot λ-aprēķinu. Tas ir līdzvērtīgs vispārēju rekursīvu funkciju izmantošanai. Čērča-Tjūringa tēze aptver vairāk aprēķinu veidu, nekā sākotnēji tika domāts. Piemēram, saistībā ar šūnu automātiem, kombinatoriem, reģistrācijas iekārtām un aizstāšanas sistēmām. 1933. gadā matemātiķi Kurts Gēdels un Žaks Herbrands izveidoja formālu definīciju klasei, ko sauc par vispārējām rekursīvajām funkcijām. Tas izmanto funkcijas, kurās ir iespējams vairāk nekā viens arguments.
Metodes izveideλ-calculus
1936. gadā Alonso baznīca izveidoja noteikšanas metodi, ko sauc par λ-calculus. Viņš bija saistīts ar naturālajiem skaitļiem. λ-aprēķinos zinātnieks noteica to kodējumu. Rezultātā tos sauc par Baznīcas numuriem. Funkciju, kas balstīta uz naturāliem skaitļiem, sauca par λ-skaitļojamu. Bija cita definīcija. Funkciju no Čērčas darba sauc par λ-skaitļojamu divos apstākļos. Pirmais izklausījās šādi: ja tas tika aprēķināts pēc Baznīcas elementiem, un otrais nosacījums bija iespēja tikt pārstāvētam ar λ-aprēķina dalībnieku.
Arī 1936. gadā, pirms pētīja kolēģa darbus, Tjūrings izveidoja teorētisko modeli abstraktajām mašīnām, kas tagad nosauktas viņa vārdā. Viņi varēja veikt aprēķinus, manipulējot ar lentes rakstzīmēm. Tas attiecas arī uz citām matemātiskām darbībām, kas atrodamas teorētiskajā datorzinātnē, piemēram, kvantu varbūtības skaitļošanā. Čērčas disertācijas funkcija tikai vēlāk tika pamatota, izmantojot Tjūringa mašīnu. Sākotnēji viņi paļāvās uz λ-aprēķinu.
Funkciju izskaitļojamība
Kad naturālie skaitļi ir atbilstoši kodēti kā rakstzīmju virknes, naturālu skaitļu funkcija tiek uzskatīta par Tjūringa izskaitļojamu, ja abstraktā mašīna ir atradusi vajadzīgo algoritmu un izdrukājusi šo funkciju uz lentes. Šāda ierīce, kuras 30. gados nebija, nākotnē tiks uzskatīta par datoru. Abstraktā Tjūringa mašīna un Čērčas tēze vēstīja par attīstības laikmetuskaitļošanas ierīces. Tika pierādīts, ka abu zinātnieku formāli definētās funkciju klases sakrīt. Tāpēc rezultātā abi apgalvojumi tika apvienoti vienā. Aprēķināmības jēdzienu spēcīgi ietekmēja arī skaitļošanas funkcijas un baznīcas tēzes. Tie kļuva arī par svarīgu matemātiskās loģikas un pierādījumu teorijas rīku.
Metodes pamatojums un problēmas
Par darbu ir pretrunīgi viedokļi. Tika savākti daudzi pierādījumi par "darba hipotēzi", ko 1936. gadā izvirzīja Čērča un Tjūrings. Taču visas zināmās metodes vai darbības jaunu, efektīvi izrēķināmu funkciju atklāšanai no dotajām bija saistītas ar mašīnu būves metodēm, kuru tolaik vēl nebija. Lai pierādītu Čērča-Tjūringa tēzi, jāsāk ar faktu, ka katrs reālistisks aprēķinu modelis ir līdzvērtīgs.
Dažādu analīžu daudzveidības dēļ to parasti uzskata par īpaši spēcīgu pierādījumu. Visi mēģinājumi precīzāk definēt intuitīvo jēdzienu par efektīvi aprēķināmu funkciju izrādījās līdzvērtīgi. Katra piedāvātā analīze ir pierādījusi, ka izceļ vienu un to pašu funkciju klasi, proti, tās, kuras var aprēķināt ar Tjūringa mašīnām. Taču daži skaitļošanas modeļi izrādījās efektīvāki laika un atmiņas lietojuma ziņā dažādiem uzdevumiem. Vēlāk tika atzīmēts, ka rekursīvo funkciju pamatjēdzieni un baznīcas tēze ir diezgan hipotētiskas.
Tēzes M
Ir svarīgi atšķirt Tjūringa tēzi no apgalvojuma, ka visu, ko var aprēķināt ar skaitļošanas ierīci, var aprēķināt tās mašīna. Otrajam variantam ir sava definīcija. Gandijs otro teikumu sauc par "tēzi M". Tas ir šādi: "Visu, ko var aprēķināt ar ierīci, var aprēķināt ar Tjūringa mašīnu." Darba šaurā nozīmē tas ir empīrisks piedāvājums, kura patiesības vērtība nav zināma. Tjūringa tēze un "tēze M" dažkārt tiek sajauktas. Otrā versija kopumā ir nepareiza. Ir aprakstītas dažādas nosacītas mašīnas, kas var aprēķināt funkcijas, kuras nav aprēķināmas Tjūringā. Ir svarīgi atzīmēt, ka pirmā tēze neietver otro, bet atbilst tās nepatiesībai.
Darba apgrieztā nozīme
Aprēķināmības teorijā Čērča tēze tiek izmantota kā aprēķinamības jēdziena apraksts ar vispārīgu rekursīvu funkciju klasi. Amerikānis Stīvens Kleins sniedza vispārīgāku formulējumu. Viņš sauca par daļēji rekursīvām visas daļējas funkcijas, kuras var aprēķināt ar algoritmiem.
Apgrieztā nozīme parasti tiek saukta par Baznīcas apgriezto tēzi. Tas ir saistīts ar faktu, ka tiek efektīvi novērtēta katra pozitīvu veselu skaitļu rekursīvā funkcija. Šaurā nozīmē tēze vienkārši apzīmē šādu iespēju. Un plašākā nozīmē tas abstrahējas no jautājuma, vai šī nosacītā mašīna tajā var pastāvēt.
Kvantu datori
Aprēķināmo funkciju jēdzieni un Čērčas tēzes kļuva par svarīgu atklājumu matemātikā, mašīnu teorijā un daudzās citās zinātnēs. Taču tehnoloģija ir daudz mainījusies un turpina uzlaboties. Tiek pieņemts, ka kvantu datori var veikt daudzus parastus uzdevumus ar mazāku laiku nekā mūsdienu datori. Taču jautājumi paliek, piemēram, apstāšanās problēma. Kvantu dators nevar uz to atbildēt. Un saskaņā ar Čērča-Tjūringa tēzi arī neviena cita skaitļošanas ierīce.
