Кіріспе

Мәселені тиімді шешу қабілеті Есептеу қабілеті – мәселені тиімді шешуге болатын мүмкіндік. Бұл математикалық логикадағы есептеу теориясы және компьютер ғылымындағы есептеулер теориясы салаларының маңызды тақырыбы. Мәселенің есептелуі мәселені шешуге арналған алгоритмнің болуымен тікелей байланысты. Ең көп зерттелген есептеу модельдері – Тьюринг есептеулері, μ-рекурсивті функциялар және лямбда-есептеу, олардың барлығы бірдей есептеу күшіне ие. Есептеудің басқа да түрлері зерттеледі: автоматтар теориясында Тьюринг машиналарынан нашар есептеу ұғымдары зерттелсе, ал Тьюринг машиналарынан күшті есептеу ұғымдары гипересептеу саласында зерттеледі.

Автоматтардың күші

Осы есептеу модельдерінің болуы арқасында, біз олардың мүмкіндіктерін шектейтін факторларды анықтай аламыз. Яғни, олар қандай тілдер кластарын қабылдай алады?

Шекті күйдегі машиналардың қуаты

Компьютерлік ғалымдар кез келген тілді, оны шекті күйдегі машина қабылдаса, тұрақты тіл деп атайды. Шекті күй машинасындағы мүмкін күйлер саны шекті болғандықтан, тұрақты емес тілді табу үшін шексіз күйлерді қажет ететін тілді құрастыруымыз керек екенін көреміз. Мұндай тілдің мысалы – "a" және "b" әріптерінің тең санын қамтитын "a" және "b" әріптерінен тұратын барлық тізбектер жиыны. Бұл тілді шекті күйдегі машина дұрыс тани алмайтынын түсіну үшін, алдымен мұндай машина M бар деп есептейік. M-де n санындағы күйлер болуы керек. Енді x тізбегін қарастырайық, ол "a" әріптерінен басталып, содан кейін "b" әріптерінен тұрады. M тізбекті x оқығанда, машинада "a" әріптерінің бірінші тізбесін оқығанда қайталанатын күй болуы керек, себебі "a" саны бар және тек n күй ғана бар, қабылдану принципі бойынша. Бұл күйді S деп атайық, ал d – машинамыздың "a" тізбегі кезінде S күйінің бірінші пайда болуынан кейінгі пайда болуына дейін оқыған "a" саны болсын. Онда S күйінің екінші рет пайда болуында, қосымша d ("where") 'a' әріптерін қоссақ, қайтадан S күйіне жететінімізді білеміз. Бұл "a" тізбегі "a" тізбегімен бірдей күйде аяқталуы керек екенін білдіреді. Демек, егер машинамыз x тізбегін қабылдаса, онда ол "a" және "b" әріптерінің тізбегін де қабылдауы керек, бірақ бұл тізбек "a" және "b" әріптерінің тең санынан тұратын тілге жатпайды. Басқаша айтқанда, M тең сандағы "a" және "b" әріптері бар тізбекті, "a" және "b" әріптерінің тең емес санынан тұратын тізбектен дұрыс ажырата алмайды. Сондықтан, бұл тілді кез келген шекті күй машинасы дұрыс қабылдай алмайтынын, демек ол тұрақты тіл емес екенін білеміз. Бұл нәтиженің жалпыланған түрі тұрақты тілдер үшін сорғы леммасы деп аталады, оны тілдердің кең кластарын шекті күй машинасымен тану мүмкін емес екенін көрсетуге болады.

Төменге қарай итергіш автоматтардың күші

Компьютерлік ғалымдар pushdown автоматтары қабылдай алатын тілді Context-free тіл деп анықтайды, оны Context-free грамматика арқылы сипаттауға болады. Біз бұл тілдің реттеліссіз екенін көрсеткен "a" мен "b" әрпінің тең санынан тұратын тізбектер жиынын pushdown автоматымен шеше аламыз. Сонымен қатар, pushdown автоматы жалпы жағдайда, шекті күйдегі машина сияқты жұмыс істей алады, сондықтан ол кез келген реттеліс тілді шеше алады. Осы есептеу моделі шекті күйдегі машиналардан әлдеқайда күшті. Дегенмен, pushdown автоматымен шеше алмайтын тілдер де бар. Бұл нәтиже реттеліссіз өрнектердегі нәтижеге ұқсас, сондықтан оны толық қарастырмаймыз. Context-free тілдер үшін Pumping lemma қолданылады. Мұндай тілдің мысалы – жай сандар жиыны.

Тоқтату мәселесі

Тоқтату мәселесі – компьютерлік ғылымдағы ең танымал мәселелердің бірі, себебі ол есептеу теориясына және күнделікті практикада компьютерлерді қалай пайдалануымызға терең ықпал етеді. Мәселе мынадай тұрғыда қойылуы мүмкін:

Тьюринг машинасының сипаттамасы және оның бастапқы кіріс деректері берілгенде, бағдарлама осы кіріс деректерімен орындалған кезде тоқтай ма (аяқталады) анықтаңыз. Басқаша айтқанда, ол тоқтамай, мәңгілікке дейін жұмыс істей береді. Бұл жерде біз жай ғана жай санның жай сан екенін немесе сөздің палиндром екенін сұрамаймыз, керісінше, жағдайды өзгертіп, бір Тьюринг машинасынан басқа Тьюринг машинасы туралы сұраққа жауап беруді сұраймыз. Барлық жағдайда осы сұраққа жауап бере алатын Тьюринг машинасының құру мүмкін емес екендігі көрсетілген (Тоқтату мәселесіне қараңыз). Яғни, белгілі бір бағдарламаның белгілі бір кіріс деректерінде тоқтайтынын барлық жағдайда білудің жалғыз жалпы жолы – оны іске қосып, тоқтауын күту. Егер ол тоқтаса, онда оның тоқтағанын білесіз. Егер ол тоқтамаса, онда ол ақырында тоқтайтынын білу мүмкін болмайды. Тьюринг машинасының барлық сипаттамаларымен және олардың ақырында тоқтайтын барлық мүмкін кіріс ағындарымен құралған тіл рекурсивті емес. Сондықтан тоқтату мәселесі есептелмейтін немесе шешілмейтін мәселе деп аталады. Тоқтату мәселесінің жалғасы Райс теоремасы болып табылады, ол берілген тілдің кез келген нақты тривиалды емес қасиетке ие болуы (жалпы жағдайда) шешілмейтіндігін көрсетеді.

Рекурсивті саналатын тілдерден тыс

Тоқтату мәселесін шешу оңай, бірақ, егер тоқтатуды анықтайтын Тьюринг машинасы, өзі тоқтамайтын Тьюринг машинасының бейнесін кіріс ретінде алғанда, шексіз жұмыс істеуі мүмкін болса. Сондықтан тоқтату тілі рекурсивті түрде санауға болады. Дегенмен, рекурсивті түрде санауға келмейтін тілдерді құрастыруға болады. Мұндай тілдің қарапайым мысалы – тоқтату тілінің толықтырғышы; яғни, кіріс жолдарымен жұптасқан барлық Тьюринг машиналары, онда Тьюринг машиналары кірісінде тоқтамайды. Бұл тілдің рекурсивті түрде санауға болмайтынын көрсету үшін, барлық мұндай Тьюринг машиналарына нақты жауап бере алатын M Тьюринг машинасының құрылғанын көзге елестетіп көріңіз, бірақ ол ақырында тоқтайтын кез келген Тьюринг машинасы үшін шексіз жұмыс істей алады. Содан кейін біз тағы бір Тьюринг машинасы құрастыра аламыз, ол осы машинаның жұмысын симуляциялайды, сонымен қатар екі бағдарламаның орындалуын біріктіре отырып, кіріске берілген машинаның орындалуын тікелей симуляциялайды. Тікелей симуляция, егер ол симуляциялайтын бағдарлама тоқтаса, тоқтайды, ал кіріс бағдарламасы ешқашан тоқтамаса, M симуляциясы тоқтайды деп болжамдаймыз, сондықтан оның параллель нұсқаларының бірі тоқтайды. Осылайша, ол тоқтату мәселесін шешеді. Бірақ, біз бұрын тоқтату мәселесінің шешілмейтінін көрсеттік. Қайшылық пайда болды, демек, M бар деген болжамымыз дұрыс емес. Сондықтан тоқтату тілінің толықтырғышы рекурсивті түрде санауға болмайды.

Конкуренттік негіздегі модельдер

Бірқатар бірмезгілде жұмыс ілеуге негізделген есептеу модельдері жасалды, оның ішінде параллель кездейсоқ кіру машинасы және Петри желісі. Бұл бірмезгілде есептеу модельдері әлі де Тьюринг машиналарымен жүзеге асырылмаған математикалық функцияларды іске асырмайды.

Есептеудің мықты модельдері

Чёрч-Тьюринг тезисі Тьюринг машинасы есептей алатын математикалық функциялардан артық функцияларды есептейтін тиімді есептеу моделінің жоқтығын болжайды. Компьютер ғалымдары Тьюрингтік есептеу шегінен асып түсетін гиперкомпьютерлердің көптеген түрлерін және есептеу модельдерін ойластырды.

Шексіз орындау

Есептеудің әрбір қадамы алдыңғы қадамға қарағанда екі есе аз уақытты қажет етеді (және үміттенсек, алдыңғы қадамға қарағанда екі есе аз энергияны қажет етеді). Егер бірінші қадамға қажетті уақытты 1/2 уақыт бірлігіне, ал бірінші қадамға қажетті энергияны 1/2 энергия бірлігіне нормалдасақ, орындалуға уақыт бірлігі (және 1 энергия бірлігі) қажет болады. Бұл шексіз қатар 1-ге жақындайды, яғни бұл Зено машинасы 1 уақыт бірлігінде (1 энергия бірлігін пайдаланып) санаулы шексіз қадамдарды орындай алады. Бұл машина сұрақталған машинаның орындалуын тікелей модельдеу арқылы тоқтату мәселесін шеше алады. Сонымен қатар, кез келген жақындасатын шексіз [дәлелді түрде шексіз болуы керек] қатар да жұмыс істейді. Егер шексіз қатар n мәніне жақындасады деп есептесек, Зено машинасы санаулы шексіз орындалуды n уақыт бірлігінде аяқтайды.

Оракул машиналары

Оракул машиналары деп аталатын машиналар әртүрлі "оракулдарға" қол жеткізе алады, олар белгілі бір шешілмейтін мәселелерге жауап береді. Мысалы, Тьюринг машинасы "тоқтау оракулына" ие болуы мүмкін, ол нақты Тьюринг машинасы берілген деректерде тоқтай ма, тоқтамай ма деген сұраққа дереу жауап береді. Бұл машиналар рекурсия теориясының орталық зерттеу нысаны болып табылады.

Гиперкомпьютерлік есептеудің шектері

Тіпті, біз елестетуге болатын автоматтардың шегін көрсететін осы машиналардың өзі де өз шектеріне жетеді. Олардың әрқайсысы Тьюринг машинасы үшін тоқтау мәселесін шеше алғанымен, өзінің тоқтау мәселесін шеше алмайды. Мысалы, Oracle машинасы басқа бір Oracle машинасы тоқтай ма деген сұраққа жауап бере алмайды.