Ang Church-Turing thesis ay tumutukoy sa konsepto ng isang mahusay, sistematiko, o mekanikal na pamamaraan sa lohika, matematika, at computer science. Binubuo ito bilang isang paglalarawan ng intuitive na konsepto ng computability at, kaugnay ng pangkalahatang recursive function, ay mas madalas na tinatawag na Church's thesis. Ito rin ay tumutukoy sa teorya ng computer-computable functions. Ang thesis ay lumitaw noong 1930s, nang ang mga computer mismo ay hindi pa umiiral. Nang maglaon, pinangalanan ito sa American mathematician na si Alonso Church at sa kanyang British na kasamahan na si Alan Turing.
Kahusayan ng paraan para makamit ang resulta
Ang unang device na kahawig ng isang modernong computer ay ang Bombie, isang makina na nilikha ng English mathematician na si Alan Turing. Ito ay ginamit upang maintindihan ang mga mensahe ng Aleman noong Ikalawang Digmaang Pandaigdig. Ngunit para sa kanyang tesis at pormalisasyon ng konsepto ng isang algorithm, gumamit siya ng mga abstract na makina, na kalaunan ay tinawag na Turing machine. Thesis presentsinteres para sa parehong mga mathematician at programmer, dahil ang ideyang ito ay nagbigay inspirasyon sa mga lumikha ng mga unang computer.
Sa teorya ng computability, ang Church-Turing thesis ay kilala rin bilang haka-haka tungkol sa kalikasan ng mga computable function. Ito ay nagsasaad na para sa anumang algorithmically computable function sa natural na mga numero, mayroong isang Turing machine na kayang i-compute ito. O, sa madaling salita, mayroong isang algorithm na angkop para dito. Ang isang kilalang halimbawa ng pagiging epektibo ng paraang ito ay ang truth table test para sa pagsubok ng tautolohiya.
Ang isang paraan upang makamit ang anumang ninanais na resulta ay tinatawag na "epektibo", "sistematiko" o "mekanikal" kung:
- Ang pamamaraan ay tinukoy sa mga tuntunin ng isang limitadong bilang ng eksaktong mga tagubilin, ang bawat pagtuturo ay ipinahayag gamit ang isang may hangganang bilang ng mga character.
- Tatakbo ito nang walang mga error, gagawa ng gustong resulta sa isang tiyak na bilang ng mga hakbang.
- Ang pamamaraan ay maaaring gawin ng isang tao nang walang tulong gamit ang anumang kagamitan maliban sa papel at lapis
- Hindi ito nangangailangan ng pang-unawa, intuwisyon o talino sa bahagi ng taong nagsasagawa ng aksyon
Mas maaga sa matematika, ang impormal na terminong "effectively computable" ay ginamit upang tumukoy sa mga function na maaaring kalkulahin gamit ang lapis at papel. Ngunit ang mismong paniwala ng algorithmic computability ay mas madaling maunawaan kaysa sa anumang kongkreto. Ngayon ito ay nailalarawan sa pamamagitan ng isang function na may natural na argumento, kung saan mayroong isang algorithm ng pagkalkula. Isa sa mga nagawa ni Alan Turing ayrepresentasyon ng isang pormal na eksaktong panaguri, sa tulong kung saan posible na palitan ang impormal, kung ginamit ang kondisyon ng kahusayan ng pamamaraan. Ginawa ng simbahan ang parehong pagtuklas.
Mga pangunahing konsepto ng recursive function
Ang pagbabago ni Turing ng mga panaguri, sa unang tingin, ay mukhang iba sa iminungkahi ng kanyang kasamahan. Ngunit bilang isang resulta, sila ay naging katumbas, sa kahulugan na ang bawat isa sa kanila ay pumipili ng parehong hanay ng mga pag-andar sa matematika. Ang Church-Turing thesis ay ang paggigiit na ang set na ito ay naglalaman ng bawat function na ang mga halaga ay maaaring makuha sa pamamagitan ng isang pamamaraan na nakakatugon sa mga kondisyon ng kahusayan. May isa pang pagkakaiba sa pagitan ng dalawang natuklasan. Iyon ay ang Simbahan ay isinasaalang-alang lamang ang mga halimbawa ng mga positibong integer, habang inilarawan ni Turing ang kanyang trabaho bilang sumasaklaw sa mga computable function na may integral o totoong variable.
Mga karaniwang recursive function
Ang orihinal na pormulasyon ng Simbahan ay nagsasaad na ang pagkalkula ay maaaring gawin gamit ang λ-calculus. Ito ay katumbas ng paggamit ng mga generic na recursive function. Ang Church-Turing thesis ay sumasaklaw sa mas maraming uri ng pagtutuos kaysa sa orihinal na inaakala. Halimbawa, nauugnay sa cellular automata, combinators, registration machine at substitution system. Noong 1933, ang mga mathematician na sina Kurt Gödel at Jacques Herbrand ay lumikha ng isang pormal na kahulugan ng isang klase na tinatawag na pangkalahatang recursive function. Gumagamit ito ng mga function kung saan posible ang higit sa isang argumento.
Paggawa ng paraanλ-calculus
Noong 1936, lumikha ang Alonso Church ng isang paraan ng pagpapasiya na tinatawag na λ-calculus. Siya ay nauugnay sa mga natural na numero. Sa loob ng λ-calculus, tinukoy ng siyentipiko ang kanilang pag-encode. Bilang resulta, tinawag silang mga numero ng Simbahan. Ang isang function batay sa natural na mga numero ay tinatawag na λ-computable. Nagkaroon ng isa pang kahulugan. Ang function mula sa thesis ng Simbahan ay tinatawag na λ-computable sa ilalim ng dalawang kondisyon. Ang una ay ganito ang tunog: kung ito ay kalkulahin sa mga elemento ng Simbahan, at ang pangalawang kundisyon ay ang posibilidad na kinakatawan ng isang miyembro ng λ-calculus.
Gayundin noong 1936, bago pag-aralan ang gawain ng kanyang kasamahan, lumikha si Turing ng isang teoretikal na modelo para sa abstract machine na ipinangalan ngayon sa kanya. Maaari silang magsagawa ng mga kalkulasyon sa pamamagitan ng pagmamanipula ng mga character sa tape. Nalalapat din ito sa iba pang mga aktibidad sa matematika na matatagpuan sa teoretikal na agham ng kompyuter, tulad ng quantum probabilistic computing. Ang tungkulin mula sa thesis ng Simbahan ay napatunayan lamang sa ibang pagkakataon gamit ang Turing machine. Noong una, umasa sila sa λ-calculus.
Function computability
Kapag ang mga natural na numero ay naaangkop na na-encode bilang mga pagkakasunud-sunod ng character, ang isang function sa mga natural na numero ay sinasabing Turing-computable kung nakita ng abstract machine ang kinakailangang algorithm at na-print ang function na ito sa tape. Ang nasabing aparato, na hindi umiiral noong 1930s, ay ituturing na isang computer sa hinaharap. Ang abstract Turing machine at thesis ng Simbahan ay nagpahayag ng isang panahon ng pag-unladmga kagamitan sa pag-compute. Napatunayan na ang mga klase ng mga function na pormal na tinukoy ng parehong mga siyentipiko ay nag-tutugma. Samakatuwid, bilang isang resulta, ang parehong mga pahayag ay pinagsama sa isa. Ang mga computational function at thesis ng Simbahan ay nagkaroon din ng malakas na impluwensya sa konsepto ng computability. Naging mahalagang kasangkapan din sila para sa mathematical logic at proof theory.
Pagbibigay-katwiran at mga problema ng pamamaraan
May mga magkasalungat na pananaw sa thesis. Maraming ebidensya ang nakolekta para sa "working hypothesis" na iminungkahi nina Church at Turing noong 1936. Ngunit ang lahat ng kilalang pamamaraan o operasyon para sa pagtuklas ng mga bagong epektibong computable na function mula sa mga ibinigay ay konektado sa mga paraan ng paggawa ng mga makina, na wala pa noon. Para patunayan ang Church-Turing thesis, magsisimula ang isang tao sa katotohanan na ang bawat makatotohanang modelo ng pagtutuos ay katumbas.
Dahil sa iba't ibang mga pagsusuri, ito ay karaniwang itinuturing na partikular na matibay na ebidensya. Ang lahat ng mga pagtatangka upang mas tiyak na tukuyin ang intuitive na paniwala ng isang epektibong computable function ay naging katumbas. Ang bawat pagsusuri na iminungkahi ay napatunayang nag-iisa sa parehong klase ng mga pag-andar, lalo na yaong mga computable ng Turing machine. Ngunit ang ilang mga modelo ng computational ay naging mas mahusay sa mga tuntunin ng oras at paggamit ng memorya para sa iba't ibang mga gawain. Nang maglaon ay nabanggit na ang mga pangunahing konsepto ng recursive function at thesis ng Simbahan ay hypothetical.
Thesis M
Mahalagang tukuyin ang pagkakaiba sa pagitan ng thesis ni Turing at ang assertion na anumang bagay na maaaring kalkulahin ng isang computing device ay maaaring kalkulahin ng makina nito. Ang pangalawang opsyon ay may sariling kahulugan. Tinawag ni Gandhi ang pangalawang pangungusap na "Thesis M". Ito ay ganito: "Anuman ang maaaring kalkulahin ng isang aparato ay maaaring kalkulahin ng isang Turing machine." Sa makitid na kahulugan ng thesis, ito ay isang empirical na proposisyon na ang halaga ng katotohanan ay hindi alam. Ang Thesis ni Turing at "Thesis M" ay minsan nalilito. Ang pangalawang bersyon ay malawak na hindi tama. Ang iba't ibang conditional machine ay inilarawan na maaaring mag-compute ng mga function na hindi Turing computable. Mahalagang tandaan na hindi kasama sa unang thesis ang pangalawa, ngunit naaayon sa kamalian nito.
Baliktad na implikasyon ng thesis
Sa teorya ng computability, ang thesis ng Simbahan ay ginagamit bilang isang paglalarawan ng ideya ng computability ng isang klase ng pangkalahatang recursive function. Ang Amerikanong si Stephen Kleene ay nagbigay ng mas pangkalahatang pormulasyon. Tinawag niyang partially recursive ang lahat ng partial function na computable ng algorithm.
Reverse implication ay karaniwang tinutukoy bilang reverse thesis ng Simbahan. Ito ay nakasalalay sa katotohanan na ang bawat recursive function ng positive integers ay mahusay na sinusuri. Sa isang makitid na kahulugan, ang isang thesis ay nagsasaad lamang ng gayong posibilidad. At sa mas malawak na kahulugan, ito ay nag-abstract mula sa tanong kung ang conditional machine na ito ay maaaring umiral dito.
Quantum computers
Ang mga konsepto ng computable function at thesis ng Simbahan ay naging isang mahalagang pagtuklas para sa matematika, machine theory at marami pang ibang agham. Ngunit ang teknolohiya ay nagbago nang malaki at patuloy na umuunlad. Ipinapalagay na ang mga quantum computer ay maaaring magsagawa ng maraming karaniwang mga gawain na may mas kaunting oras kaysa sa mga modernong. Ngunit nananatili ang mga tanong, tulad ng paghinto ng problema. Hindi ito masasagot ng isang quantum computer. At, ayon sa Church-Turing thesis, wala ring ibang computing device.
