Тюринг толықтығы және есептеулер теориясы

Кіріспе

Есептеу жүйесінің Тьюринг машиналарын симуляциялау қабілеті
Оракул машиналары арқылы салыстырмалы есептеу теориясында осы терминді қолдану

Есептеу теориясында деректерді өңдеу ережелерінің жүйесі (мысалы, есептеу моделі, компьютердің нұсқаулар жиынтығы, бағдарламалау тілі немесе жасушалық автомат) Тьюринг толық немесе есептеу универсалды деп аталады, егер ол кез келген Тьюринг машинасын (ағылшын математигі және компьютер ғалымы Алан Тьюринг жасаған) симуляциялай алса. Бұл дегеніміз, бұл жүйе басқа деректерді өңдеу ережелерін таниды немесе шеше алады. Тьюринг толықтығы мұндай деректерді өңдеу ережесі жиынтығының күшін білдіру тәсілі ретінде қолданылады. Бүгінгі таңдағы бағдарламалау тілдерінің барлығы дерлік Тьюринг толық. Туысты ұғым – Тьюрингтік эквиваленттілік: егер P, Q-ны және Q, P-ні симуляциялай алса, екі компьютер P және Q эквивалентті деп аталады. Черч-Тьюринг тезисінде кез келген функцияның мәнін алгоритм арқылы есептеуге болатын болса, оны Тьюринг машинасы арқылы да есептеуге болады делінеді, сондықтан нақты әлемдегі кез келген компьютер Тьюринг машинасын симуляциялай алса, ол Тьюринг машинасына эквивалентті болады. Универсалды Тьюринг машинасы кез келген Тьюринг машинасын және, демек, кез келген нақты әлемдегі компьютердің таза есептеу аспектілерін симуляциялау үшін қолданылуы мүмкін. Бір нәрсенің Тьюринг толық екенін көрсету үшін, оны кейбір Тьюринг толық жүйелерді симуляциялау үшін қолдануға болатынын көрсету жеткілікті. Физикалық жүйеде шексіз жад болуы мүмкін емес, бірақ шекті жадтың шектеулері ескерілмесе, көптеген бағдарламалау тілдері Тьюринг толық болып табылады.

Математикадан тыс қолданыс

Күнделікті қолданыста "Тьюринг толық" және "Тьюринг баламалы" терминдері, кез келген нақты әлемдегі мақсатына қарай қолданылатын компьютер немесе компьютерлік тіл, кез келген басқа нақты әлемдегі мақсатына қарай қолданылатын компьютердің немесе компьютерлік тілдің есептеулік аспектілерін шамамен имитациялай алады дегенді білдіреді. Шын өмірде бұл есептеуді виртуализациялау және эмуляциялаудың практикалық түсініктеріне алып келеді. Бүгінгі күнге дейін құрастырылған нақты компьютерлерді, жад ретінде "лента" қолданатын бір ленталы Тьюринг машинасы сияқты функционалдық тұрғыдан талдауға болады; осылайша, олардың жұмысын жеткілікті деңгейде абстракциялау арқылы байланысты математиканы қолдануға мүмкіндік туады. Дегенмен, нақты компьютерлердің физикалық ресурстары шектеулі болғандықтан, олар тек сызықтық шектеулі автоматтар толықтығына ие. Ал, әмбебап компьютердің абстракциясы – Тьюринг толық нұсқаулар жиынтығы, шексіз жад және шексіз уақытқа қол жетімділікпен анықталатын құрылғы ретінде қарастырылады.

Тарих

Тьюрингтің толықтығы маңызды, себебі есептеу құрылғысының нақты әлемдегі кез келген дизайны универсалды Тьюринг машинасымен модельделуі мүмкін. Church-Turing тезисіне сәйкес, бұл математика заңы, яғни универсалды Тьюринг машинасы, принципі бойынша, кез келген басқа бағдарламаланатын компьютер орындай алатын кез келген есептеуді жүзеге асыра алады. Бұл бағдарламаны жазуға қажетті күш-жігер туралы, немесе машинаның есептеуді орындауына кеткен уақыт туралы, немесе машинаның есептеумен байланысы жоқ қабілеттері туралы ештеңе айтпайды. Чарльз Бэббидждің аналитикалық машинасы (1830-шы жылдар) егер сол кезде жасалған болса, алғашқы толық Тьюринг машинасы болар еді. Бэббидж машинаның үлкен есептеулерге қабілетті екенін, соның ішінде қарапайым логикалық қорытындыларды жасауды бағалады, бірақ ол басқа машинаның одан жақсы жасай алмайтынын түсінбеді. 1830-шы жылдардан 1940-шы жылдарға дейін қосу және көбейту машиналары сияқты механикалық есептеу машиналары жасалды және жетілдірілді, бірақ олар шартты тармақтануды орындай алмады, сондықтан Тьюринг толық емес еді. 19 ғасырдың соңында Леопольд Кронекер алғашқы рекурсивті функцияларды анықтап, есептеу мүмкіндігі туралы түсініктерді қалыптастырды. Бұл функцияларды жаттап алып, есептеу арқылы табуға болады, бірақ олар әмбебап компьютер жасау үшін жеткіліксіз, себебі оларды есептеуге арналған нұсқаулар шексіз циклге мүмкіндік бермейді. 20 ғасырдың басында Дэвид Гилберт математиканың барлық саласын машинамен орындалатын нақты аксиомалармен және нақты логикалық қорытынды ережелерімен аксиомаландыру бағдарламасын бастады. Көп ұзамай, кез келген аксиомалардың салдарынан шығару үшін шағын қорытынды ережелерінің жиынтығы жеткілікті екені анықталды. Курт Гёдель 1930 жылы бұл ережелердің барлық теоремаларды жасауға жеткілікті екенін дәлелдеді. Есептеудің нақты түсінігі Гёдельдің толық еместік теоремасынан бастап оқшауланды. Бұл теорема аксиомалық жүйелердің теоремаларын шығару үшін есептеу туралы ой жүгірту кезіндегі шектеулерін көрсетті. Чирч және Тьюринг дербес түрде Хилберттің Entscheidungsproblem (шешім проблемасы) шешілмейтінін көрсетті, осылайша толық еместік теоремасының есептеу ядросын анықтады. Бұл жұмыс, Гёдельдің жалпы рекурсивті функциялар жөніндегі еңбегімен бірге, қарапайым нұсқаулар жиынтығының бар екенін көрсетті, олар біріктірілген кезде кез келген есептеуді жүзеге асыра алады. Гёдельдің еңбегі есептеу ұғымының мәнінде бірегей екенін көрсетті. 1941 жылы Конрад Цузе Z3 компьютерін аяқтады. Зюзе сол кезде Тьюрингтің есептеу мүмкіндігі туралы жұмысымен таныс болған жоқ. Атап айтқанда, Z3 шартты секіруге арналған арнайы құрылғыларға ие болған жоқ, осылайша оны Тьюринг толықтығынан айырды. Алайда, 1998 жылы Рохас Z3 шартты секіруді және, демек, теориялық тұрғыдан толық Тьюрингті модельдей алатынын көрсетті. Бұл үшін оның ленталық бағдарламасы әр тармақтың екі жағындағы барлық мүмкін жолдарды орындауға жеткілікті ұзын болуы керек еді. Шартты тармақтануға қабілетті алғашқы компьютер, демек, тәжірибеде толық Тьюринг машинасы – 1946 жылғы ENIAC болды. Zuse-дің Z4 компьютері 1945 жылы жұмыс істеді, бірақ ол 1950 жылға дейін шартты тармақтануды қолдамады.

Turing completeness is significant in that every real world design for a computing device can be simulated by a universal Turing machine. The Church–Turing thesis states that this is a law of mathematics that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can. This says nothing about the effort needed to write the program, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation. Charles Babbage's analytical engine (1830s) would have been the first Turing complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing complete. In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions that compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction that could be performed by a machine. Soon it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved by Kurt Gödel in 1930 to be enough to produce every theorem. The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation that deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable, thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique. In 1941 Konrad Zuse completed the Z3 computer. Zuse was not familiar with Turing's work on computability at the time. In particular, the Z3 lacked dedicated facilities for a conditional jump, thereby precluding it from being Turing complete. However, in 1998, it was shown by Rojas that the Z3 is capable of simulating conditional jumps, and therefore Turing complete in theory. To do this, its tape program would have to be long enough to execute every possible path through both sides of every branch. The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the ENIAC in 1946. Zuse's Z4 computer was operational in 1945, but it did not support conditional branching until 1950.

Есептеу теориясы

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

Тьюринг оракулдары

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

Цифрлық физика

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

Тюрингтік толық емес тілдер

Тьюрингтік толық емес көптеген есептеу тілдері бар. Мұндай мысалдың бірі – тұрақты тілдер жиынтығы, олар тұрақты өрнектер арқылы жасалады және шекті автоматтармен танылады. Қорытынды автоматтардың күштірек, бірақ әлі де Тьюрингтік толық емес кеңейтімі – программаны компиляциялаудың алғашқы кезеңінде талдау ағаштарын құру үшін жиі қолданылатын pushdown автоматтар мен контекстсіз грамматикалар санаты. Басқа мысалдар Direct3D және OpenGL кеңейтімдеріне енген пиксельдік шейдер тілдерінің ерте нұсқаларын қамтиды. Charity және Epigram сияқты толыққанды функционалдық бағдарламалау тілдерінде барлық функциялар толық және міндетті түрде аяқталуы керек. Charity категориялық теорияға негізделген типтік жүйе мен басқару құрылымдарын пайдаланады, ал Epigram тәуелді типтерді қолданады. LOOP тілі тек примитивті рекурсивті функцияларды есептеу үшін жасалған. Бұлардың барлығы жалпы есептелетін функциялардың дұрыс ішкі жиындықтарын есептейді, себебі жалпы есептелетін функциялардың толық жиынтығы есептеу арқылы санауға келмейді. Сондай-ақ, осы тілдердегі барлық функциялар толық болғандықтан, рекурсивті түрде саналатын жиынтықтардың алгоритмдерін осы тілдерде жазу мүмкін емес, бұл Тьюринг машиналарынмен салыстырғанда айқын айырмашылық. (Типтелмеген) ламбдалық есептеу Тьюрингтік толық болғанымен, қарапайым типтелген ламбдалық есептеу Тьюрингтік толық емес.