Չերչ-Թյուրինգի թեզը վերաբերում է տրամաբանության, մաթեմատիկայի և համակարգչային գիտության արդյունավետ, համակարգված կամ մեխանիկական մեթոդի հայեցակարգին: Այն ձևակերպված է որպես հաշվարկելիության ինտուիտիվ հայեցակարգի նկարագրություն և ընդհանուր ռեկուրսիվ ֆունկցիաների առնչությամբ ավելի հաճախ կոչվում է Չերչի թեզ։ Խոսքը վերաբերում է նաև համակարգչային հաշվողական ֆունկցիաների տեսությանը։ Թեզը հայտնվեց 1930-ականներին, երբ համակարգիչներն իրենք դեռ գոյություն չունեին։ Ավելի ուշ այն անվանվել է ամերիկացի մաթեմատիկոս Ալոնսո Չերչի և նրա բրիտանացի գործընկեր Ալան Թյուրինգի պատվին։
Արդյունքի հասնելու մեթոդի արդյունավետությունը
Առաջին սարքը, որը նման էր ժամանակակից համակարգչին, Bombie-ն էր՝ անգլիացի մաթեմատիկոս Ալան Թյուրինգի ստեղծած մեքենան: Երկրորդ համաշխարհային պատերազմի ժամանակ այն օգտագործվել է գերմանական հաղորդագրությունները վերծանելու համար։ Բայց իր թեզի և ալգորիթմի հայեցակարգի պաշտոնականացման համար նա օգտագործեց վերացական մեքենաներ, որոնք հետագայում կոչվեցին Թյուրինգի մեքենաներ: Թեզը ներկայացնում էհետաքրքրություն ինչպես մաթեմատիկոսների, այնպես էլ ծրագրավորողների համար, քանի որ այս գաղափարը ոգեշնչել է առաջին համակարգիչների ստեղծողներին:
Հաշվարկելիության տեսության մեջ Չերչ-Թյուրինգի թեզը հայտնի է նաև որպես հաշվարկելի ֆունկցիաների բնույթի մասին ենթադրություն: Այն նշում է, որ բնական թվերի վրա ալգորիթմորեն հաշվելի ցանկացած ֆունկցիայի համար կա Թյուրինգի մեքենա, որը կարող է այն հաշվարկել։ Կամ, այլ կերպ ասած, կա դրա համար հարմար ալգորիթմ։ Այս մեթոդի արդյունավետության հայտնի օրինակ է տավտոլոգիայի փորձարկման ճշմարտության աղյուսակի թեստը:
Ցանկացած արդյունքի հասնելու միջոցը կոչվում է «արդյունավետ», «համակարգային» կամ «մեխանիկական», եթե՝
- Մեթոդը սահմանվում է ճշգրիտ հրահանգների վերջավոր թվով, յուրաքանչյուր հրահանգ արտահայտվում է վերջավոր թվով նիշերի միջոցով:
- Այն կաշխատի առանց սխալների, որոշակի քանակությամբ քայլերով կտա ցանկալի արդյունք:
- Մեթոդը կարող է իրականացվել մարդու կողմից առանց որևէ այլ սարքավորման, բացի թղթից և մատիտից
- Այն գործողությունը կատարող անձի ըմբռնում, ինտուիցիա կամ հնարամտություն չի պահանջում
Ավելի վաղ մաթեմատիկայի մեջ «արդյունավետորեն հաշվարկելի» ոչ պաշտոնական տերմինն օգտագործվում էր մատիտով և թղթով հաշվարկվող գործառույթներին մատնանշելու համար: Բայց ալգորիթմական հաշվարկելիության գաղափարն ավելի ինտուիտիվ էր, քան որևէ կոնկրետ բան: Այժմ այն բնութագրվում էր բնական արգումենտով ֆունկցիայով, որի համար կա հաշվարկման ալգորիթմ։ Ալան Թյուրինգի ձեռքբերումներից էրձևականորեն ճշգրիտ պրեդիկատի ներկայացում, որի օգնությամբ հնարավոր կլինի փոխարինել ոչ պաշտոնականը, եթե օգտագործվի մեթոդի արդյունավետության պայմանը։ Եկեղեցին արել է նույն հայտնագործությունը։
Ռեկուրսիվ ֆունկցիաների հիմնական հասկացությունները
Թյուրինգի պրեդիկատների փոփոխությունն առաջին հայացքից տարբերվում էր իր գործընկերոջ առաջարկածից: Բայց արդյունքում պարզվեց, որ դրանք համարժեք են, այն առումով, որ նրանցից յուրաքանչյուրն ընտրում է մաթեմատիկական ֆունկցիաների նույն բազմությունը։ Չերչ-Թյուրինգի թեզը պնդում է, որ այս հավաքածուն պարունակում է բոլոր գործառույթները, որոնց արժեքները կարելի է ձեռք բերել արդյունավետության պայմանները բավարարող մեթոդով: Երկու հայտնագործությունների միջև ևս մեկ տարբերություն կար. Հենց այն էր, որ Չերչը դիտարկում էր միայն դրական ամբողջ թվերի օրինակները, մինչդեռ Թյուրինգը նկարագրում էր իր աշխատանքը որպես ինտեգրալ կամ իրական փոփոխականով հաշվարկելի ֆունկցիաների ծածկում:
Ընդհանուր ռեկուրսիվ ֆունկցիաներ
Եկեղեցու բնօրինակ ձևակերպման մեջ ասվում է, որ հաշվարկը կարող է կատարվել λ-հաշվի միջոցով: Սա համարժեք է ընդհանուր ռեկուրսիվ ֆունկցիաների օգտագործմանը: Չերչ-Թյուրինգի թեզն ընդգրկում է հաշվարկների ավելի շատ տեսակներ, քան ենթադրվում էր սկզբում: Օրինակ՝ կապված բջջային ավտոմատների, կոմբինատորների, գրանցման մեքենաների և փոխարինող համակարգերի հետ։ 1933 թվականին մաթեմատիկոսներ Կուրտ Գյոդելը և Ժակ Հերբրանդը ստեղծեցին դասի պաշտոնական սահմանումը, որը կոչվում է ընդհանուր ռեկուրսիվ ֆունկցիաներ։ Այն օգտագործում է գործառույթներ, որտեղ հնարավոր է մեկից ավելի արգումենտ:
Մեթոդի ստեղծումλ-հաշվ
1936 թվականին Ալոնսո եկեղեցին ստեղծեց որոշման մեթոդ, որը կոչվում էր λ-հաշվարկ: Նա կապված էր բնական թվերի հետ։ λ-հաշվի շրջանակներում գիտնականը որոշել է դրանց կոդավորումը: Արդյունքում դրանք կոչվում են Եկեղեցու համարներ: Բնական թվերի վրա հիմնված ֆունկցիան կոչվում էր λ-հաշվելի։ Մեկ այլ սահմանում կար. Չերչի թեզի ֆունկցիան կոչվում է λ-հաշվելի երկու պայմանով. Առաջինը հնչում էր այսպես. եթե այն հաշվարկված էր Եկեղեցու տարրերով, իսկ երկրորդ պայմանը λ-հաշվի անդամով ներկայացված լինելու հնարավորությունն էր։
Նաև 1936 թվականին, նախքան իր գործընկերոջ աշխատանքը ուսումնասիրելը, Թյուրինգը ստեղծեց տեսական մոդել աբստրակտ մեքենաների համար, որոնք այժմ կոչվում են իր անունով: Նրանք կարող էին հաշվարկներ կատարել ժապավենի նիշերը շահարկելով: Սա վերաբերում է նաև տեսական համակարգչային գիտության մեջ հայտնաբերված այլ մաթեմատիկական գործունեությանը, ինչպիսին է քվանտային հավանականության հաշվարկը: Չերչի թեզի գործառույթը միայն ավելի ուշ հիմնավորվեց Թյուրինգի մեքենայի միջոցով: Սկզբում նրանք հիմնվում էին λ-հաշվի վրա։
Ֆունկցիայի հաշվելիություն
Երբ բնական թվերը պատշաճ կերպով կոդավորված են որպես նիշերի հաջորդականություն, բնական թվերի վրա ֆունկցիան համարվում է Թյուրինգով հաշվարկելի, եթե վերացական մեքենան գտնի պահանջվող ալգորիթմը և տպի այս ֆունկցիան ժապավենի վրա: Նման սարքը, որը գոյություն չուներ 1930-ականներին, ապագայում համակարգիչ կհամարվեր։ Թյուրինգի վերացական մեքենան և Չերչի թեզը ազդարարեցին զարգացման դարաշրջանհաշվողական սարքեր. Ապացուցվեց, որ երկու գիտնականների կողմից պաշտոնապես սահմանված ֆունկցիաների դասերը համընկնում են։ Հետևաբար, արդյունքում երկու հայտարարություններն էլ միավորվեցին մեկի մեջ։ Հաշվողական գործառույթները և Չերչի թեզը նույնպես մեծ ազդեցություն են ունեցել հաշվողականության հայեցակարգի վրա: Նրանք նաև կարևոր գործիք դարձան մաթեմատիկական տրամաբանության և ապացույցների տեսության համար:
Մեթոդի հիմնավորումը և խնդիրները
Թեզի վերաբերյալ կան հակասական տեսակետներ. Բազմաթիվ ապացույցներ են հավաքվել 1936 թվականին Չերչի և Թյուրինգի կողմից առաջարկված «աշխատանքային վարկածի» համար։ Բայց բոլոր հայտնի մեթոդները կամ գործողությունները տվյալներից նոր արդյունավետ հաշվարկելի ֆունկցիաներ հայտնաբերելու համար կապված էին մեքենաների կառուցման մեթոդների հետ, որոնք այն ժամանակ գոյություն չունեին։ Չերչ-Թյուրինգի թեզն ապացուցելու համար պետք է ելնել այն փաստից, որ հաշվարկման յուրաքանչյուր իրատեսական մոդել համարժեք է:
Տարբեր վերլուծությունների բազմազանության պատճառով սա, ընդհանուր առմամբ, համարվում է հատկապես ուժեղ ապացույց: Արդյունավետ հաշվարկելի ֆունկցիայի ինտուիտիվ հասկացությունն ավելի ճշգրիտ սահմանելու բոլոր փորձերը համարժեք են ստացվել: Առաջարկված յուրաքանչյուր վերլուծություն ցույց է տվել, որ առանձնացնում է ֆունկցիաների միևնույն դասը, մասնավորապես՝ Թյուրինգի մեքենաներով հաշվելի գործառույթներ: Սակայն որոշ հաշվողական մոդելներ ավելի արդյունավետ են եղել տարբեր առաջադրանքների համար ժամանակի և հիշողության օգտագործման առումով: Հետագայում նշվեց, որ ռեկուրսիվ ֆունկցիաների հիմնական հասկացությունները և Չերչի թեզը բավականին հիպոթետիկ են։
«Թեզ M»
Կարևոր է տարբերակել Թյուրինգի թեզը և այն պնդումը, որ այն ամենը, ինչ կարելի է հաշվարկել հաշվողական սարքի միջոցով, կարող է հաշվարկվել դրա մեքենայի միջոցով: Երկրորդ տարբերակն ունի իր սահմանումը. Երկրորդ նախադասությունը Գանդին անվանում է «Թեզ M»: «Այն, ինչ կարելի է հաշվարկել սարքի միջոցով, կարող է հաշվարկվել Թյուրինգի մեքենայի միջոցով»: Թեզի նեղ իմաստով այն էմպիրիկ դրույթ է, որի ճշմարտացիության արժեքը անհայտ է: Թյուրինգի թեզը և «Թեզը M»-ը երբեմն շփոթվում են: Երկրորդ տարբերակը հիմնականում սխալ է։ Նկարագրվել են տարբեր պայմանական մեքենաներ, որոնք կարող են հաշվարկել Թյուրինգի հաշվառելի գործառույթներ: Կարևոր է նշել, որ առաջին թեզը չի ենթադրում երկրորդը, այլ համահունչ է դրա կեղծությանը։
Թեզի հակադարձ ենթատեքստ
Հաշվարկելիության տեսության մեջ Չերչի թեզը օգտագործվում է որպես ընդհանուր ռեկուրսիվ ֆունկցիաների դասի կողմից հաշվարկելիության հասկացության նկարագրություն։ Ավելի ընդհանուր ձեւակերպում է տվել ամերիկացի Սթիվեն Քլինը. Նա մասնակի ռեկուրսիվ է անվանել ալգորիթմներով հաշվելի բոլոր մասնակի ֆունկցիաները։
Հակադարձ ենթատեքստը սովորաբար կոչվում է Եկեղեցու հակադարձ թեզ: Այն կայանում է նրանում, որ դրական ամբողջ թվերի յուրաքանչյուր ռեկուրսիվ ֆունկցիա արդյունավետորեն գնահատվում է: Նեղ իմաստով թեզը պարզապես նշանակում է նման հնարավորություն։ Եվ ավելի լայն իմաստով, դա վերացական է այն հարցից, թե արդյոք այս պայմանական մեքենան կարող է գոյություն ունենալ դրանում:
Քվանտային համակարգիչներ
Հաշվարկվող ֆունկցիաների հասկացությունները և Չերչի թեզը կարևոր հայտնագործություն դարձան մաթեմատիկայի, մեքենաների տեսության և շատ այլ գիտությունների համար: Սակայն տեխնոլոգիաները շատ են փոխվել և շարունակում են կատարելագործվել: Ենթադրվում է, որ քվանտային համակարգիչները կարող են շատ սովորական առաջադրանքներ կատարել ավելի քիչ ժամանակով, քան ժամանակակիցները։ Բայց հարցերը մնում են, ինչպիսին է կանգառի խնդիրը: Քվանտային համակարգիչը չի կարող պատասխանել դրան: Եվ, ըստ Church-Turing թեզի, ոչ մի այլ հաշվողական սարք:
