Черк-Тюринг тезисі логика, математика және информатикадағы тиімді, жүйелі немесе механикалық әдіс тұжырымдамасына сілтеме жасайды. Ол есептеудің интуитивті тұжырымдамасының сипаттамасы ретінде тұжырымдалған және жалпы рекурсивті функцияларға қатысты жиі Черч тезисі деп аталады. Ол сондай-ақ компьютермен есептелетін функциялар теориясына жатады. Диссертация 1930 жылдары, компьютерлердің өзі әлі болмаған кезде пайда болды. Кейінірек ол американдық математик Алонсо Черч пен оның британдық әріптесі Алан Тьюрингтің құрметіне аталған.
Нәтижеге жету әдісінің тиімділігі
Қазіргі компьютерге ұқсайтын алғашқы құрылғы ағылшын математигі Алан Тьюринг жасаған Bombie машинасы болды. Ол Екінші дүниежүзілік соғыс кезінде неміс хабарламаларын шешу үшін пайдаланылды. Бірақ оның тезисі және алгоритм тұжырымдамасын формализациялау үшін ол кейінірек Тьюринг машиналары деп аталатын дерексіз машиналарды пайдаланды. Дипломдық жұмыс ұсынадыматематиктерді де, бағдарламашыларды да қызықтырды, өйткені бұл идея алғашқы компьютерлерді жасаушыларды шабыттандырды.
Есептеу теориясында Черч-Тюринг тезисі есептелетін функциялардың табиғаты туралы болжам ретінде де белгілі. Онда натурал сандардағы кез келген алгоритмдік есептелетін функция үшін оны есептей алатын Тьюринг машинасы бар екені айтылған. Немесе, басқаша айтқанда, оған қолайлы алгоритм бар. Бұл әдіс тиімділігінің белгілі мысалы - таутологияны тексеруге арналған ақиқат кестесі сынағы.
Кез келген қалаған нәтижеге жету жолы "тиімді", "жүйелі" немесе "механикалық" деп аталады, егер:
- Әдіс нақты нұсқаулардың ақырғы санымен көрсетілген, әрбір нұсқау таңбалардың шектеулі санын пайдаланып көрсетіледі.
- Ол қатесіз жұмыс істейді, белгілі бір қадамдар санымен қажетті нәтижені береді.
- Әдісті адамның көмегінсіз қағаз бен қарындаштан басқа кез келген жабдықпен орындауға болады
- Бұл әрекетті орындаушыдан түсінуді, интуицияны немесе тапқырлықты қажет етпейді
Бұрын математикада «тиімді түрде есептелетін» бейресми термині қарындаш пен қағазбен есептеуге болатын функцияларға сілтеме жасау үшін қолданылған. Бірақ алгоритмдік есептеудің өзі нақты кез келген нәрсеге қарағанда интуитивті болды. Енді ол табиғи аргументі бар функциямен сипатталды, ол үшін есептеу алгоритмі бар. Алан Тьюрингтің жетістіктерінің бірі болдыформальды дәл предикатты ұсыну, оның көмегімен әдістің тиімділік шарты қолданылса, бейресмиді ауыстыруға болады. Шіркеу де дәл осындай жаңалық ашты.
Рекурсивті функциялардың негізгі түсініктері
Тьюрингтің предикаттарды өзгертуі, бір қарағанда, әріптесі ұсынғаннан басқаша көрінді. Бірақ нәтижесінде олардың әрқайсысы бірдей математикалық функциялар жиынтығын таңдайтын мағынада олар эквивалентті болып шықты. Черч-Тюринг тезисі - бұл жиынтықта мәндерін тиімділік шарттарын қанағаттандыратын әдіспен алуға болатын әрбір функция бар деген тұжырым. Екі жаңалықтың тағы бір айырмашылығы болды. Тьюринг өз жұмысын интегралдық немесе нақты айнымалымен есептелетін функцияларды қамту ретінде сипаттаған кезде Черч тек натурал сандар мысалдарын қарастырды.
Жалпы рекурсивті функциялар
Шіркеудің бастапқы тұжырымы есептеуді λ-есепті пайдаланып жасауға болатынын айтады. Бұл жалпы рекурсивті функцияларды пайдаланумен бірдей. Черч-Тюринг тезисі бастапқыда ойлағаннан гөрі есептеудің көбірек түрлерін қамтиды. Мысалы, ұялы автоматтарға, комбинаторларға, тіркеу машиналарына және ауыстыру жүйелеріне қатысты. 1933 жылы математиктер Курт Годель мен Жак Хербранд жалпы рекурсивті функциялар деп аталатын класстың ресми анықтамасын жасады. Ол бірнеше аргумент мүмкін болатын функцияларды пайдаланады.
Әдіс жасауλ-есеп
1936 жылы Алонсо Черч λ-есеп деп аталатын анықтау әдісін жасады. Ол натурал сандармен байланысты болды. λ-есептің ішінде ғалым олардың кодталуын анықтады. Нәтижесінде олар шіркеу нөмірлері деп аталады. Натурал сандарға негізделген функция λ-есептелетін деп аталды. Басқа анықтама болды. Черч тезисіндегі функция екі жағдайда λ-есептелетін деп аталады. Біріншісі былай естілді: егер ол шіркеу элементтері бойынша есептелсе, ал екінші шарт λ-есептің мүшесімен ұсынылу мүмкіндігі болды.
Сонымен қатар 1936 жылы әріптесінің жұмысын зерттемес бұрын Тьюринг қазір оның атымен аталған абстрактілі машиналар үшін теориялық модель жасады. Олар лентадағы таңбаларды өңдеу арқылы есептеулер жүргізе алатын. Бұл кванттық ықтималдық есептеулер сияқты теориялық информатикада табылған басқа математикалық әрекеттерге де қатысты. Черч тезисіндегі функция кейінірек Тьюринг машинасының көмегімен дәлелденді. Бастапқыда олар λ-есепке сүйенді.
Функцияны есептеу мүмкіндігі
Натурал сандар таңбалар тізбегі ретінде сәйкес кодталғанда, егер дерексіз машина қажетті алгоритмді тауып, бұл функцияны таспаға басып шығарса, натурал сандардағы функция Тьюринг арқылы есептелетін деп аталады. 1930 жылдары болмаған мұндай құрылғы болашақта компьютер болып есептелетін еді. Абстрактілі Тьюринг машинасы және Черч тезисі даму дәуірін жарияладыесептеуіш құрылғылар. Екі ғалым формальды түрде анықтаған функциялар кластарының сәйкес келетіні дәлелденді. Сондықтан, нәтижесінде екі мәлімдеме де бір жерге біріктірілді. Есептеу функциялары мен Черч тезисі де есептеу мүмкіндігінің тұжырымдамасына қатты әсер етті. Олар сонымен қатар математикалық логика мен дәлелдеу теориясының маңызды құралы болды.
Әдістің негіздемесі мен мәселелері
Дисертацияға қарама-қайшы көзқарастар бар. 1936 жылы Черч пен Тьюринг ұсынған «жұмыс гипотезасына» көптеген дәлелдер жиналды. Бірақ берілгендерден жаңа тиімді есептелетін функцияларды ашудың барлық белгілі әдістері немесе операциялары ол кезде болмаған машиналарды жасау әдістерімен байланысты болды. Черч-Тюринг тезисін дәлелдеу үшін есептеудің әрбір нақты моделінің эквивалентті екендігінен бастау керек.
Әртүрлі талдаулардың әртүрлілігіне байланысты бұл әдетте ерекше күшті дәлел болып саналады. Тиімді есептелетін функцияның интуитивті түсінігін дәлірек анықтаудың барлық әрекеттері баламалы болып шықты. Ұсынылған әрбір талдау функциялардың бірдей класын, атап айтқанда Тьюринг машиналары арқылы есептелетіндерді бөліп көрсетуге мүмкіндік берді. Бірақ кейбір есептеу модельдері әртүрлі тапсырмалар үшін уақыт пен жадты пайдалану тұрғысынан тиімдірек болып шықты. Кейінірек рекурсивті функциялардың негізгі ұғымдары мен Черч тезисі біршама гипотетикалық екені атап өтілді.
Дисертациялық М
Тьюринг тезисі мен есептеу құрылғысы арқылы есептелетін кез келген нәрсені оның машинасымен есептеуге болады деген тұжырымды ажырата білу маңызды. Екінші нұсқаның өзіндік анықтамасы бар. Ганди екінші сөйлемді «М тезисі» деп атайды. Бұл былай болады: «Құрылғымен есептелетін нәрсені Тьюринг машинасымен есептеуге болады». Диссертацияның тар мағынасында бұл шындықтың мәні белгісіз эмпирикалық ұсыныс. Тьюрингтің тезисі мен «М тезисі» кейде шатастырылады. Екінші нұсқа мүлдем дұрыс емес. Туринг есептелмейтін функцияларды есептей алатын әртүрлі шартты машиналар сипатталған. Айта кету керек, бірінші тезис екіншісін тудырмайды, бірақ оның жалғандығына сәйкес келеді.
Дисертацияның кері әсері
Есептеу теориясында Черч тезисі жалпы рекурсивті функциялар класы бойынша есептелушілік ұғымының сипаттамасы ретінде пайдаланылады. Американдық Стивен Клин жалпылама тұжырым жасады. Ол алгоритмдер арқылы есептелетін барлық ішінара функцияларды ішінара рекурсивті деп атады.
Кері ықпалды әдетте шіркеудің кері тезисі деп атайды. Бұл оң бүтін сандардың әрбір рекурсивті функциясының тиімді бағалануында жатыр. Тар мағынада тезис мұндай мүмкіндікті білдіреді. Ал кеңірек мағынада бұл шартты машина онда болуы мүмкін бе деген сұрақтан абстракциялайды.
Кванттық компьютерлер
Есептелетін функциялар ұғымдары және Черч тезисі математика, машина теориясы және басқа да көптеген ғылымдар үшін маңызды жаңалық болды. Бірақ технология көп өзгерді және жетілдірілуде. Кванттық компьютерлер қазіргі заманғы компьютерлерге қарағанда аз уақытпен көптеген жалпы тапсырмаларды орындай алады деп болжанады. Бірақ тоқтау мәселесі сияқты сұрақтар қалады. Кванттық компьютер оған жауап бере алмайды. Сондай-ақ, Черч-Тюринг тезисі бойынша, басқа есептеуіш құрылғы да жоқ.
