Tasnifu ya Kugeuza Kanisa inarejelea dhana ya mbinu bora, ya utaratibu, au ya kimakanika katika mantiki, hisabati, na sayansi ya kompyuta. Imetungwa kama maelezo ya dhana angavu ya utangamano na, kuhusiana na utendaji wa jumla wa kujirudia, mara nyingi huitwa tasnifu ya Kanisa. Pia inarejelea nadharia ya vitendaji vya kompyuta. Thesis ilionekana katika miaka ya 1930, wakati kompyuta zenyewe hazikuwepo. Baadaye lilipewa jina la Mwanahisabati Mmarekani Alonso Church na Mwingereza mwenzake Alan Turing.
Ufanisi wa mbinu ya kufikia matokeo
Kifaa cha kwanza kilichofanana na kompyuta ya kisasa kilikuwa Bombie, mashine iliyoundwa na mtaalamu wa hisabati Mwingereza Alan Turing. Ilitumiwa kufafanua ujumbe wa Ujerumani wakati wa Vita vya Kidunia vya pili. Lakini kwa nadharia yake na urasimishaji wa dhana ya algorithm, alitumia mashine za kufikirika, ambazo baadaye ziliitwa mashine za Turing. Thesis inatoamaslahi kwa wanahisabati na watayarishaji programu, kwa kuwa wazo hili liliwahimiza waundaji wa kompyuta za kwanza.
Katika nadharia ya utangamano, tasnifu ya Kugeuzwa Kanisa pia inajulikana kama dhana kuhusu asili ya utendaji unaoweza kukokotwa. Inasema kwamba kwa kazi yoyote ya algorithmically computable kwenye nambari za asili, kuna mashine ya Turing yenye uwezo wa kuihesabu. Au, kwa maneno mengine, kuna algorithm inayofaa kwake. Mfano unaojulikana sana wa ufanisi wa mbinu hii ni jaribio la jedwali la ukweli kwa ajili ya kupima tautolojia.
Njia ya kufikia matokeo yoyote unayotaka inaitwa "ifaayo", "taratibu" au "mitambo" ikiwa:
- Njia hii imebainishwa kulingana na idadi kamili ya maagizo kamili, kila maagizo yanaonyeshwa kwa idadi maalum ya herufi.
- Itaendeshwa bila hitilafu, itatoa matokeo unayotaka katika idadi fulani ya hatua.
- Mbinu hiyo inaweza kufanywa na binadamu bila kusaidiwa na kifaa chochote isipokuwa karatasi na penseli
- Hahitaji uelewa, angavu au werevu kwa upande wa mtu anayetekeleza kitendo
Hapo awali katika hisabati, istilahi isiyo rasmi "inayoweza kutambulika ipasavyo" ilitumiwa kurejelea vitendaji vinavyoweza kukokotwa kwa penseli na karatasi. Lakini dhana yenyewe ya utangamano wa algorithmic ilikuwa angavu zaidi kuliko kitu chochote halisi. Sasa ilikuwa na sifa ya kazi yenye hoja ya asili, ambayo kuna algorithm ya hesabu. Moja ya mafanikio ya Alan Turing ilikuwauwakilishi wa kitabiri rasmi, kwa msaada wa ambayo itawezekana kuchukua nafasi ya isiyo rasmi, ikiwa hali ya ufanisi wa njia inatumiwa. Kanisa lilifanya ugunduzi sawa.
Dhana za kimsingi za vitendaji kujirudi
Badiliko la Turing la vihusishi, kwa mtazamo wa kwanza, lilionekana tofauti na lile lililopendekezwa na mwenzake. Lakini kwa sababu hiyo, waligeuka kuwa sawa, kwa maana kwamba kila mmoja wao huchagua seti sawa ya kazi za hisabati. Tasnifu ya Kubadilisha Kanisa ni madai kwamba seti hii ina kila kazi ambayo maadili yake yanaweza kupatikana kwa njia inayokidhi masharti ya ufanisi. Kulikuwa na tofauti nyingine kati ya uvumbuzi mbili. Ilikuwa ni kwamba Kanisa lilizingatia tu mifano ya nambari kamili chanya, huku Turing alielezea kazi yake kama inayoshughulikia utendaji unaoweza kutambulika kwa kigezo muhimu au halisi.
vitendaji vya kawaida vya kujirudia
Muundo asilia wa Kanisa unasema kuwa hesabu inaweza kufanywa kwa kutumia λ-calculus. Hii ni sawa na kutumia vitendaji vya kawaida vya kujirudi. Tasnifu ya Kugeuza Kanisa inashughulikia aina nyingi za hesabu kuliko ilivyofikiriwa hapo awali. Kwa mfano, kuhusiana na otomatiki ya rununu, viunganishi, mashine za usajili na mifumo mbadala. Mnamo 1933, wanahisabati Kurt Gödel na Jacques Herbrand waliunda ufafanuzi rasmi wa darasa liitwalo utendakazi wa jumla wa kujirudi. Inatumia vitendaji ambapo zaidi ya hoja moja inawezekana.
Kuunda mbinuλ-calculus
Mnamo 1936, Kanisa la Alonso liliunda mbinu ya uamuzi inayoitwa λ-calculus. Alihusishwa na nambari za asili. Ndani ya λ-calculus, mwanasayansi aliamua usimbuaji wao. Matokeo yake, zinaitwa nambari za Kanisa. Chaguo za kukokotoa kulingana na nambari asilia ziliitwa λ-computable. Kulikuwa na ufafanuzi mwingine. Kazi kutoka tasnifu ya Kanisa inaitwa λ-computable chini ya masharti mawili. Ya kwanza ilisikika hivi: ikiwa ilihesabiwa kwa vipengele vya Kanisa, na sharti la pili lilikuwa uwezekano wa kuwakilishwa na mshiriki wa λ-calculus.
Pia mnamo 1936, kabla ya kusoma kazi ya mwenzake, Turing aliunda muundo wa kinadharia wa mashine za kufikirika ambazo sasa zimepewa jina lake. Wangeweza kufanya mahesabu kwa kuchezea wahusika kwenye kanda. Hii inatumika pia kwa shughuli zingine za hisabati zinazopatikana katika sayansi ya kompyuta ya nadharia, kama vile kompyuta ya uwezekano wa quantum. Kazi kutoka kwenye tasnifu ya Kanisa ilithibitishwa baadaye tu kwa kutumia mashine ya Turing. Hapo awali, walitegemea λ-calculus.
Tangamano la kazi
Nambari asilia zinaposimbwa ipasavyo kama mfuatano wa herufi, chaguo la kukokotoa kwenye nambari asilia inasemekana kuwa linaweza kukokotwa ikiwa mashine ya kufikirika ilipata algoriti inayohitajika na kuchapisha chaguo hili la kukokotoa kwenye kanda. Kifaa kama hicho, ambacho hakikuwepo katika miaka ya 1930, katika siku zijazo kitazingatiwa kuwa kompyuta. Mashine ya Turing na tasnifu ya Kanisa ilitangaza enzi ya maendeleovifaa vya kompyuta. Ilithibitishwa kuwa madarasa ya kazi yaliyofafanuliwa rasmi na wanasayansi wote wawili yanafanana. Kwa hivyo, kama matokeo, taarifa zote mbili ziliunganishwa kuwa moja. Kazi za kimahesabu na tasnifu ya Kanisa pia ilikuwa na ushawishi mkubwa juu ya dhana ya utangamano. Pia zikawa zana muhimu ya mantiki ya hisabati na nadharia ya uthibitisho.
Uhalali na matatizo ya mbinu
Kuna maoni yanayokinzana kuhusu nadharia hii. Ushahidi mwingi ulikusanywa kwa ajili ya "dhahania inayofanya kazi" iliyopendekezwa na Kanisa na Turing mnamo 1936. Lakini njia zote zinazojulikana au shughuli za kugundua kazi mpya zinazoweza kutekelezwa kutoka kwa wale waliopewa ziliunganishwa na njia za mashine za ujenzi, ambazo hazikuwepo wakati huo. Ili kuthibitisha tasnifu ya Kugeuza Kanisa, mtu anaanza na ukweli kwamba kila kielelezo halisi cha hesabu ni sawa.
Kutokana na aina mbalimbali za uchanganuzi, huu kwa ujumla huchukuliwa kuwa ushahidi dhabiti. Majaribio yote ya kufafanua kwa ufasaha zaidi dhana angavu ya chaguo za kukokotoa inayoweza kukokotwa kwa ufanisi yaligeuka kuwa sawa. Kila uchanganuzi ambao umependekezwa umethibitisha kubainisha aina sawa za utendakazi, yaani zile ambazo zinaweza kuunganishwa na mashine za Turing. Lakini baadhi ya mifano ya computational iligeuka kuwa na ufanisi zaidi katika suala la wakati na utumiaji wa kumbukumbu kwa kazi tofauti. Baadaye ilibainika kuwa dhana za kimsingi za utendaji wa kujirudi na tasnifu ya Kanisa ni ya kidhahania.
Thesis M
Ni muhimu kutofautisha kati ya nadharia ya Turing na madai kwamba chochote kinachoweza kukokotwa kwa kifaa cha kompyuta kinaweza kukokotwa kwa mashine yake. Chaguo la pili lina ufafanuzi wake mwenyewe. Gandhi anaita sentensi ya pili "Thesis M". Inakwenda kama hii: "Chochote kinachoweza kukokotwa na kifaa kinaweza kukokotwa na mashine ya Turing." Kwa maana finyu ya thesis, ni pendekezo la kimajaribio ambalo thamani yake ya ukweli haijulikani. Thesis ya Turing na "Thesis M" wakati mwingine huchanganyikiwa. Toleo la pili sio sahihi kabisa. Mashine mbalimbali zenye masharti zimeelezewa ambazo zinaweza kukokotoa vitendaji ambavyo haviwezi kuunganishwa kwa kutumia Turing. Ni muhimu kutambua kwamba tasnifu ya kwanza haijumuishi ya pili, bali inaendana na uwongo wake.
Badili maana ya thesis
Katika nadharia ya upatanifu, tasnifu ya Kanisa inatumika kama maelezo ya dhana ya utangamano na darasa la utendaji wa jumla wa kujirudia. Mmarekani Stephen Kleene alitoa uundaji wa jumla zaidi. Aliita kipengele cha kujirudiarudia kwa sehemu zote kuwa kinaweza kuunganishwa na algoriti.
Kidokezo cha kinyume kwa kawaida hujulikana kama nadharia ya kinyume ya Kanisa. Inatokana na ukweli kwamba kila utendakazi unaojirudia wa nambari chanya hutathminiwa kwa ufanisi. Kwa maana nyembamba, nadharia inaashiria tu uwezekano kama huo. Na kwa maana pana zaidi, inatoka kwenye swali la iwapo mashine hii yenye masharti inaweza kuwepo ndani yake.
Kompyuta za kiasi
Dhana za kazi zinazoweza kukokotwa na tasnifu ya Kanisa ikawa ugunduzi muhimu wa hisabati, nadharia ya mashine na sayansi nyingine nyingi. Lakini teknolojia imebadilika sana na inaendelea kuboreka. Inachukuliwa kuwa kompyuta za quantum zinaweza kufanya kazi nyingi za kawaida kwa muda mdogo kuliko za kisasa. Lakini maswali yanabaki, kama vile shida ya kuacha. Kompyuta ya quantum haiwezi kujibu. Na, kulingana na nadharia ya Church-Turing, hakuna kifaa kingine cha kompyuta pia.
