Teza Church-Turing i referohet konceptit të një metode efikase, sistematike ose mekanike në logjikë, matematikë dhe shkenca kompjuterike. Ai është formuluar si një përshkrim i konceptit intuitiv të llogaritshmërisë dhe, në lidhje me funksionet e përgjithshme rekursive, quhet më shpesh teza e Church. Ai gjithashtu i referohet teorisë së funksioneve të llogaritshme nga kompjuteri. Teza u shfaq në vitet 1930, kur vetë kompjuterët nuk ekzistonin ende. Më vonë u emërua sipas matematikanit amerikan Alonso Church dhe kolegut të tij britanik Alan Turing.
Efikasiteti i metodës për të arritur rezultatin
Pajisja e parë që i ngjante një kompjuteri modern ishte Bombie, një makinë e krijuar nga matematikani anglez Alan Turing. Është përdorur për të deshifruar mesazhet gjermane gjatë Luftës së Dytë Botërore. Por për tezën e tij dhe formalizimin e konceptit të një algoritmi, ai përdori makina abstrakte, të quajtura më vonë makina Turing. Teza paraqetinteres për matematikanët dhe programuesit, pasi kjo ide frymëzoi krijuesit e kompjuterëve të parë.
Në teorinë e llogaritshmërisë, teza Church-Turing njihet gjithashtu si hamendësimi për natyrën e funksioneve të llogaritshme. Ai thotë se për çdo funksion të llogaritshëm algoritmikisht në numrat natyrorë, ekziston një makinë Turing e aftë për ta llogaritur atë. Ose, me fjalë të tjera, ekziston një algoritëm i përshtatshëm për të. Një shembull i njohur i efektivitetit të kësaj metode është testi i tabelës së së vërtetës për testimin e tautologjisë.
Një mënyrë për të arritur çdo rezultat të dëshiruar quhet "efektive", "sistematike" ose "mekanike" nëse:
- Metoda është e specifikuar në terma të një numri të kufizuar instruksionesh të sakta, çdo instruksion shprehet duke përdorur një numër të kufizuar karakteresh.
- Do të funksionojë pa gabime, do të prodhojë rezultatin e dëshiruar në një numër të caktuar hapash.
- Metoda mund të kryhet nga një njeri pa ndihmë me ndonjë pajisje tjetër përveç letrës dhe lapsit
- Nuk kërkon mirëkuptim, intuitë apo zgjuarsi nga ana e personit që kryen veprimin
Më parë në matematikë, termi joformal "i llogaritshëm në mënyrë efektive" u përdor për t'iu referuar funksioneve që mund të llogariten me laps dhe letër. Por vetë nocioni i llogaritshmërisë algoritmike ishte më intuitiv se çdo gjë konkrete. Tani ai karakterizohej nga një funksion me një argument natyror, për të cilin ekziston një algoritëm llogaritjeje. Një nga arritjet e Alan Turing ishteparaqitje e një kallëzuesi zyrtarisht të saktë, me ndihmën e të cilit do të mund të zëvendësohej ai joformal, nëse përdoret kushti i efikasitetit të metodës. Kisha bëri të njëjtin zbulim.
Konceptet themelore të funksioneve rekursive
Ndryshimi i kallëzuesve të Turingut, në pamje të parë, dukej ndryshe nga ai i propozuar nga kolegu i tij. Por si rezultat, ato doli të ishin ekuivalente, në kuptimin që secili prej tyre zgjedh të njëjtin grup funksionesh matematikore. Teza Church-Turing është pohimi se ky grup përmban çdo funksion, vlerat e të cilit mund të merren me një metodë që plotëson kushtet e efikasitetit. Kishte një ndryshim tjetër midis dy zbulimeve. Ishte se Church mori parasysh vetëm shembuj të numrave të plotë pozitivë, ndërsa Turing e përshkroi punën e tij si mbulim i funksioneve të llogaritshme me një ndryshore integrale ose reale.
Funksionet e zakonshme rekursive
Formulimi origjinal i Kishës thotë se llogaritja mund të bëhet duke përdorur llogaritjen λ. Kjo është e barabartë me përdorimin e funksioneve gjenerike rekursive. Teza Church-Turing mbulon më shumë lloje llogaritjeje sesa mendohej fillimisht. Për shembull, në lidhje me automatet celulare, kombinatorët, makinat e regjistrimit dhe sistemet e zëvendësimit. Në vitin 1933, matematikanët Kurt Gödel dhe Jacques Herbrand krijuan një përkufizim zyrtar të një klase të quajtur funksione rekursive të përgjithshme. Ai përdor funksione ku janë të mundshme më shumë se një argument.
Krijimi i një metodeλ-llogaritje
Në vitin 1936, Kisha Alonso krijoi një metodë përcaktimi të quajtur λ-llogaritje. Ai ishte i lidhur me numrat natyrorë. Brenda llogaritjes λ, shkencëtari përcaktoi kodimin e tyre. Si rezultat, ata quhen numra të kishës. Një funksion i bazuar në numra natyrorë quhej λ-i llogaritshëm. Kishte një përkufizim tjetër. Funksioni nga teza e Church quhet λ-i llogaritshëm në dy kushte. I pari tingëllonte kështu: nëse llogaritej me elementë të Kishës dhe kushti i dytë ishte mundësia për t'u përfaqësuar nga një anëtar i llogaritjes λ.
Gjithashtu në vitin 1936, përpara se të studionte punën e kolegut të tij, Turing krijoi një model teorik për makinat abstrakte që tani emërtohen sipas tij. Ata mund të kryejnë llogaritjet duke manipuluar karakteret në kasetë. Kjo vlen edhe për aktivitete të tjera matematikore që gjenden në shkencën teorike kompjuterike, të tilla si llogaritja kuantike probabilistike. Funksioni nga teza e Church u vërtetua vetëm më vonë duke përdorur një makinë Turing. Fillimisht, ata u mbështetën në llogaritjen λ.
Llogaritshmëria e funksionit
Kur numrat natyrorë janë të koduar siç duhet si sekuenca karakteresh, një funksion në numrat natyrorë thuhet se është i llogaritshëm me Turing nëse makina abstrakte ka gjetur algoritmin e kërkuar dhe e ka printuar këtë funksion në shirit. Një pajisje e tillë, e cila nuk ekzistonte në vitet 1930, në të ardhmen do të konsiderohej një kompjuter. Makina abstrakte Turing dhe teza e Church lajmëruan një epokë zhvillimipajisje kompjuterike. U vërtetua se klasat e funksioneve të përcaktuara zyrtarisht nga të dy shkencëtarët përkojnë. Prandaj, si rezultat, të dyja deklaratat u kombinuan në një. Funksionet llogaritëse dhe teza e Church patën gjithashtu një ndikim të fortë në konceptin e llogaritshmërisë. Ata gjithashtu u bënë një mjet i rëndësishëm për logjikën matematikore dhe teorinë e provës.
Justifikimi dhe problemet e metodës
Ka pikëpamje kontradiktore mbi tezën. Prova të shumta u mblodhën për "hipotezën e punës" të propozuar nga Church dhe Turing në 1936. Por të gjitha metodat ose operacionet e njohura për zbulimin e funksioneve të reja në mënyrë efektive të llogaritshme nga ato të dhëna ishin të lidhura me metodat e ndërtimit të makinave, të cilat nuk ekzistonin atëherë. Për të vërtetuar tezën Church-Turing, duhet nisur nga fakti se çdo model realist llogaritjeje është ekuivalent.
Për shkak të shumëllojshmërisë së analizave të ndryshme, kjo përgjithësisht konsiderohet të jetë një provë veçanërisht e fortë. Të gjitha përpjekjet për të përcaktuar më saktë nocionin intuitiv të një funksioni efektivisht të llogaritshëm rezultuan të ishin ekuivalente. Çdo analizë që është propozuar ka dëshmuar se veçon të njëjtën klasë funksionesh, përkatësisht ato që janë të llogaritshme nga makinat Turing. Por disa modele llogaritëse rezultuan më efikase për sa i përket kohës dhe përdorimit të kujtesës për detyra të ndryshme. Më vonë u vu re se konceptet bazë të funksioneve rekursive dhe teza e Kishës janë mjaft hipotetike.
Teza M
Është e rëndësishme të bëhet dallimi midis tezës së Turingut dhe pohimit se çdo gjë që mund të llogaritet nga një pajisje kompjuterike mund të llogaritet nga makina e saj. Opsioni i dytë ka përkufizimin e vet. Gandhi e quan fjalinë e dytë "Thesis M". Ajo shkon kështu: "Çfarëdo që mund të llogaritet nga një pajisje mund të llogaritet nga një makinë Turing". Në kuptimin e ngushtë të tezës, është një propozim empirik, vlera e së cilës është e panjohur. Teza e Turingut dhe "Teza M" ndonjëherë ngatërrohen. Versioni i dytë është përgjithësisht i pasaktë. Janë përshkruar makina të ndryshme të kushtëzuara që mund të llogarisin funksione që nuk janë të llogaritshme nga Turing. Është e rëndësishme të theksohet se teza e parë nuk përfshin të dytën, por është në përputhje me falsitetin e saj.
Ndikim i kundërt i tezës
Në teorinë e llogaritshmërisë, teza e Church përdoret si një përshkrim i nocionit të llogaritshmërisë nga një klasë funksionesh rekursive të përgjithshme. Amerikani Stephen Kleene dha një formulim më të përgjithshëm. Ai i quajti pjesërisht rekurzive të gjitha funksionet e pjesshme të llogaritshme me algoritme.
Ndikimi i kundërt zakonisht quhet teza e kundërt e Kishës. Ai qëndron në faktin se çdo funksion rekurziv i numrave të plotë pozitiv vlerësohet në mënyrë efikase. Në një kuptim të ngushtë, një tezë thjesht tregon një mundësi të tillë. Dhe në një kuptim më të gjerë, ai abstrakton nga pyetja nëse kjo makinë e kushtëzuar mund të ekzistojë në të.
Kompjuterë kuantikë
Konceptet e funksioneve të llogaritshme dhe teza e Church u bënë një zbulim i rëndësishëm për matematikën, teorinë e makinave dhe shumë shkenca të tjera. Por teknologjia ka ndryshuar shumë dhe vazhdon të përmirësohet. Supozohet se kompjuterët kuantikë mund të kryejnë shumë detyra të zakonshme me më pak kohë se ato moderne. Por pyetjet mbeten, siç është problemi i ndalimit. Një kompjuter kuantik nuk mund t'i përgjigjet asaj. Dhe, sipas tezës Church-Turing, asnjë pajisje tjetër kompjuterike.
