Тюрингтен асып түсетін есептеу модельдері

Кіріспе

Есептеу модельдері
Гиперкомпьютерлік немесе супер-Тьюрингтік есептеу – Тьюрингтік есептеу арқылы есептеуге болмайтын нәтижелерді бере алатын есептеудің гипотетикалық модельдерінің жиынтығы. Мысалы, тоқтау туралы мәселені шеше алатын машина гиперкомпьютер болар еді; сондай-ақ, Пеано арифметикасындағы әрбір тұжырымды дұрыс бағалай алатын машина да сондай болар еді. Чёрч-Тьюринг тезисінде математик қалам мен қағазды қолданып, шектеулі қарапайым алгоритмдер жиынтығымен есептей алатын кез келген "есептеуге болатын" функцияны Тьюринг машинасы есептей алады делінеді. Гиперкомпьютерлер Тьюринг машинасы есептей алмайтын функцияларды есептейді, демек, Чёрч-Тьюринг мағынасында олар есептелмейді. Техникалық тұрғыдан алғанда, кездейсоқ Тьюринг машинасының нәтижесі есептеуге келмейді; алайда, гиперкомпьютерлік әдебиеттердің көп бөлігі кездейсоқ емес, есептеуге келмейтін функцияларды есептеуге баса назар аударады.

Тарих

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

Мемлекеттік кеңістік

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

Модельдер

Гиперкомпьютерлік модельдер пайдалы, бірақ, мүмкін, іске асырылмайтын (мысалы, Тьюрингтің бастапқы оракул машиналарынан) бастап, одан да аз пайдалы, бірақ "іске асырылуы мүмкін" кездейсоқ функция генераторларына (мысалы, кездейсоқ Тьюринг машинасы) дейін ауысады.

Есептелмейтін кіріс немесе қара қорап компоненттері

Есептелмейтін, оракулдік Чейтин тұрақтысының (тоқтау мәселесінің шешімін кодтайтын сандардың шексіз тізбегі бар сан) білімі бар жүйе кіріс ретінде көптеген пайдалы шешілмейтін мәселелерді шеше алады; есептелмейтін кездейсоқ сан генераторы бар жүйе кіріс ретінде кездейсоқ есептелмейтін функцияларды құра алады, бірақ, әдетте, тоқтау мәселесі сияқты «пайдалы» есептелмейтін функцияларды мағыналы түрде шеше алады деп есептелмейді. Гиперкомпьютерлердің сан алуан түрлері бар, соның ішінде:

Тьюрингтің 1939 жылы анықтаған түпнұсқалық оракул машиналары. Нақты компьютер (идеалданған аналогтық компьютердің бір түрі) физика жалпы нақты айнымалыларды (тек есептелмейтін нақтыларды ғана емес) қабылдаса және олардың бірі қандай да бір жолмен пайдалы (кездейсоқ емес) есептеу үшін «пайдалануға» болатын болса, гиперкомпьютерлік есептеулерді орындай алады. Бұл физиканың өте ерекше заңдарын қажет етуі мүмкін (мысалы, Чейтин тұрақтысы сияқты оракулдік мәні бар өлшенетін физикалық тұрақты), сондай-ақ нақты сандық физикалық шаманы кез келген дәлдікпен өлшеу қабілетін қажет етеді, бірақ стандартты физика мұндай дәлдіктің өлшеулерін теориялық тұрғыдан мүмкін емес етеді. Сол сияқты, егер нейрондық желінің салмақ функциясында Чейтин тұрақтысы дәл енгізілген болса, ол тоқтау мәселесін шеше алады, бірақ бұл нақты есептеулерге негізделген гиперкомпьютерлік модельдерге тән физикалық қиындықтарға ұшырайды. Кейбір тұйық логикаға негізделген «тұйық Тьюринг машиналары» анықтама бойынша тоқтау мәселесін кездейсоқ түрде шеше алады, бірақ олардың тоқтау мәселесін шешу қабілеті машинаның сипаттамасында тікелей ескерілмейді; мұндай жағдай машиналардың бастапқы сипаттамасындағы «кемшілік» ретінде қарастырылады. Сонымен қатар, «әділ нондертерминизм» деп аталатын ұсынылған модель есептелмейтін функцияларды оракулдік есептеуге мүмкіндік беруі мүмкін, себебі мұндай жүйелердің кейбіреулері, анықтама бойынша, «әділсіз» ішкі жүйенің мәңгілікке созылуына себеп болатын қабылдамау кірістерін анықтау үшін оракулдік қабілетке ие. Дмитрий Тарановский Тьюринг машинасына оракул ретінде жылдам өсетін функциясы бар дәстүрлі емес финитистік талдаудың финитистік моделін ұсынды. Осы және одан да күрделі модельдердің көмегімен ол екінші реттік арифметиканы түсіндіре алды. Бұл модельдерге есептелмейтін кіріс қажет, мысалы, физикалық құбылыстарды тудыратын процесс, онда құбылыстар арасындағы интервал есептелмейтіндей үлкен жылдамдықпен өседі. Сол сияқты, шексіз нондертерминизм моделінің бір ерекше түсіндірмесі, анықтама бойынша, «агенттің» тұрақтанған уақытының ұзақтығы негізінен белгісіз, сондықтан модель ішінде оның есептелмейтіндей ұзақ уақытқа созылатынын дәлелдеу мүмкін емес.

Turing's original oracle machines, defined by Turing in 1939. A real computer (a sort of idealized analog computer) can perform hypercomputation if physics admits general real variables (not just computable reals), and these are in some way "harnessable" for useful (rather than random) computation. This might require quite bizarre laws of physics (for example, a measurable physical constant with an oracular value, such as Chaitin's constant), and would require the ability to measure the real valued physical value to arbitrary precision, though standard physics makes such arbitrary precision measurements theoretically infeasible. Similarly, a neural net that somehow had Chaitin's constant exactly embedded in its weight function would be able to solve the halting problem, but is subject to the same physical difficulties as other models of hypercomputation based on real computation. Certain fuzzy logic based "fuzzy Turing machines" can, by definition, accidentally solve the halting problem, but only because their ability to solve the halting problem is indirectly assumed in the specification of the machine; this tends to be viewed as a "bug" in the original specification of the machines. Similarly, a proposed model known as fair nondeterminism can accidentally allow the oracular computation of noncomputable functions, because some such systems, by definition, have the oracular ability to identify reject inputs that would "unfairly" cause a subsystem to run forever. Dmytro Taranovsky has proposed a finitistic model of traditionally non finitistic branches of analysis, built around a Turing machine equipped with a rapidly increasing function as its oracle. By this and more complicated models he was able to give an interpretation of second order arithmetic. These models require an uncomputable input, such as a physical event generating process where the interval between events grows at an uncomputably large rate. Similarly, one unorthodox interpretation of a model of unbounded nondeterminism posits, by definition, that the length of time required for an "Actor" to settle is fundamentally unknowable, and therefore it cannot be proven, within the model, that it does not take an uncomputably long period of time.

"Түкісіз есептеу қадамдары" модельдері

Дұрыс жұмыс істеу үшін төмендегі машиналардың кейбір есептеулері нақты шексіз, жай ғана шексіз емес, шекті физикалық кеңістік пен ресурстарды қажет етеді; керісінше, Тьюринг машинасымен тоқтаған кез келген есептеу үшін тек шекті физикалық кеңістік пен ресурстар ғана қажет болады. Бұл – шекті уақыт ішінде шексіз көп қадамдарды орындай алатын Тьюринг машинасы, бұл супертапсырма деп аталады. Тек қана шексіз қадамдармен жұмыс істеу жеткіліксіз. Мұндай математикалық модельдің бірі – Зенон машинасы (Зенонның парадоксынан шабыттанған). Зенон машинасы өзінің бірінші есептеу қадамын (мысалы) 1 минут ішінде, екіншісін – ½ минут ішінде, үшіншісін – ¼ минут ішінде, және т.б. орындайды. 1 + ½ + ¼ + (геометриялық қатар) қосындысын есептегенде, машинаның барлығы 2 минут ішінде шексіз көп қадам жасағанын көреміз. Шагрирдің сөзіне сәйкес, Зенон машиналары физикалық парадокстар тудырады және оның күйі [0, 2) аралығының бір жақты ашық кезеңінен тыс логикалық тұрғыдан анықталмайды, демек, есептеу басталғаннан кейін 2 минуттан кейін нақты анықталмайды. Уақыт саяхатының (жабық уақыт тәрізді қисықтардың (CTC) болуы) өзінен гиперкомпьютерлік процестерді мүмкін ететіні табиғи көрінеді. Алайда, бұл солай емес, себебі CTC (өздігінен) шексіз есептеуге қажетті шексіз сақтау көлемін қамтамасыз етпейді. Дегенмен, CTC аймағын салыстырмалы гиперкомпьютерлік есептеулер үшін пайдалануға болатын уақыт-кеңістіктер бар. 1992 жылғы мақалада айтылғандай, Malament–Hogarth кеңістігінде немесе айналып тұрған қара тесік төңірегінде жұмыс істейтін компьютер теориялық тұрғыдан қара тесік ішіндегі бақылаушы үшін Тьюринг машинасымен шешілмейтін есептеулерді орындай алады. CTC-ге қол жеткізу PSPACE толық проблемаларын жылдам шешуге мүмкіндік береді, бұл күрделілік класы Тьюринг машинасымен шешілгенімен, көбінесе есептеу жағынан қиын деп саналады.

Кванттық модельдер

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

"Ақырында түзетілетін" жүйелер

Кейбір физикалық жүзеге асырылатын жүйелер әрқашан дұрыс жауапқа ұмтылады, бірақ олардың бір кемшілігі бар: олар көбінесе бұрыс жауап береді және қате жауаппен едәуір ұзақ мерзімге тоқтап қалады, содан кейін ғана қателікті түзетеді. 1960 жылдардың ортасында Э. Марк Голд пен Хиллари Путнам индуктивті шешімдердің модельдерін (сәйкесінше, "шектелген рекурсивті функционалдар" және "қате іздеу предикаттары") тәуелсіз түрде ұсынды. Бұл модельдер кейбір рекурсивті емес сандар немесе тілдер жиындарын (рекурсивті түрде саналатын тілдер жиындары да оның ішінде) "шекте оқуға" мүмкіндік береді; алайда, анықтама бойынша, тек рекурсивті сандар немесе тілдер жиындарын ғана Тьюринг машинасы анықтай алады. Машина кез келген оқылатын жиын үшін дұрыс жауапқа белгілі бір уақыт ішінде тұрақтанса да, оны рекурсивті болса ғана дұрыс деп мойындауға болады; әйтпесе, дұрыстығын анықтау үшін машинаны мәңгілікке жұмыс істету қажет, сондай-ақ оның жауабын ешқашан қайталамағанын байқау керек. Путнам бұл жаңа түсіндіруді "эмпирикалық" предикаттар класы деп атап, былай деді: "Егер біз әрқашан соңғы жауаптың дұрыс екенін қабылдасақ, шектеулі қателер жасасақ та, ақырында дұрыс жауапқа жетеміз. (Дегенмен, егер біз дұрыс жауапқа (шектелген тізбектің соңына) жетсек те, дұрыс жауапқа ие екенімізге толық сенімді бола алмаймыз.)" Шектеулі процедураны қайталаудың әсерін зерттеді, бұл кез келген арифметикалық предикатты есептеуге мүмкіндік береді. Шуберт: "Интуитивті тұрғыдан, қайталанатын шектеулі идентификацияны жоғары деңгейдегі индуктивті шешімдеу ретінде қарастыруға болады, оны төменгі деңгейдегі индуктивті шешімдеу машиналарын құрайтын, үнемі өсіп келе жатқан қауымдастық бірлесіп орындайды". Символдар тізбегі шекте есептелуі мүмкін, егер универсалды Тьюринг машинасының шекті, мүмкін тоқтамайтын бағдарламасы тізбектің әрбір символын біртіндеп шығарса. Бұл π-нің және басқа да есептелетін нақты сандардың екілік кеңеюін қамтиды, бірақ есептелмейтін барлық нақты сандарды жоққа шығарады. Сипаттамалық өлшемдер теориясында дәстүрлі түрде қолданылатын "Монотонды Тьюринг машиналары" бұрынғы нәтижелерін өңдей алмайды; ал Юрген Шмидхубер анықтаған жалпыланған Тьюринг машиналары мұны істей алады. Ол конструктивті сипатталатын символдар тізбектерін жалпыланған Тьюринг машинасының шекті, тоқтамайтын бағдарламасы бар тізбектер ретінде анықтайды, сонда кез келген шығыс символы ақырында конвергенцияланады; яғни, белгілі бір шекті бастапқы уақыт аралығынан кейін ол өзгермейді. Курт Гёдельдің (1931) алғаш көрсеткен шектеулеріне байланысты, тоқтату бағдарламасымен конвергенция уақытын болжау мүмкін емес болуы мүмкін, әйтпесе тоқтату мәселесі шешілген болар еді. Шмидхубер бұл тәсілді формалды түрде сипатталатын немесе конструктивті есептелетін ғаламдардың немесе барлық нәрсенің конструктивті теорияларының жиынтығын анықтау үшін пайдаланады. Жалпыланған Тьюринг машиналары Спекер тізбегін бағалау арқылы тоқтату мәселесінің дұрыс шешіміне ақырында жете алады.

Some physically realizable systems will always eventually converge to the correct answer, but have the defect that they will often output an incorrect answer and stick with the incorrect answer for an uncomputably large period of time before eventually going back and correcting the mistake. In mid 1960s, E Mark Gold and Hilary Putnam independently proposed models of inductive inference (the "limiting recursive functionals" and "trial and error predicates", respectively). These models enable some nonrecursive sets of numbers or languages (including all recursively enumerable sets of languages) to be "learned in the limit"; whereas, by definition, only recursive sets of numbers or languages could be identified by a Turing machine. While the machine will stabilize to the correct answer on any learnable set in some finite time, it can only identify it as correct if it is recursive; otherwise, the correctness is established only by running the machine forever and noting that it never revises its answer. Putnam identified this new interpretation as the class of "empirical" predicates, stating: "if we always 'posit' that the most recently generated answer is correct, we will make a finite number of mistakes, but we will eventually get the correct answer. (Note, however, that even if we have gotten to the correct answer (the end of the finite sequence) we are never sure that we have the correct answer.)" studied the effects of iterating the limiting procedure; this allows any arithmetic predicate to be computed. Schubert wrote, "Intuitively, iterated limiting identification might be regarded as higher order inductive inference performed collectively by an ever growing community of lower order inductive inference machines." A symbol sequence is computable in the limit if there is a finite, possibly non halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π and of every other computable real, but still excludes all noncomputable reals. The 'Monotone Turing machines' traditionally used in description size theory cannot edit their previous outputs; generalized Turing machines, as defined by Jürgen Schmidhuber, can. He defines the constructively describable symbol sequences as those that have a finite, non halting program running on a generalized Turing machine, such that any output symbol eventually converges; that is, it does not change any more after some finite initial time interval. Due to limitations first exhibited by Kurt Gödel (1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the halting problem could be solved. Schmidhuber uses this approach to define the set of formally describable or constructively computable universes or constructive theories of everything. Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a Specker sequence.