Тюринг машини и рекурсивни функции
Обсъдихме няколко различни методи за конструиране на примитивни рекурсивни функции. Въпреки това, той не е съвсем ясно как този клас е широк. Сега ние показваме, че тя включва всички бързо изчислимите функции.
Теорема 75. Всяка функция. изчислима на една машина на Тюринг е не повече от примитивно рекурсивни (дължина на входния) времето е примитивно рекурсивни.
Припомнете си, че ние считаме, на входа и на изхода на дума от единици и нули на Тюринг машина. Като аргументите и стойностите са примитивни рекурсивни функции на теоремата ще има смисъл само, ако ние сме съгласни да се идентифицират с думи и цифри. Както вече споменахме, ние идентифицираме думата Броят п, който се получава след отстраняване на най-високата малко 1 в двоичното представяне на N + 1.
Когато симулиране на работата на машина на Тюринг с програма ние кодирани статус на машината от четири числа (код лявата страна на лентата, на код дясната страна на лентата, на държавата и на писмото под главата). В този случай, това е удобно за такова кодиране. от лявата страна на лентата, ние решихме, че рекорден брой в системата брой, в който основата е равен на броя на знаците в азбуката на машината, а разликата се счита за нула; в дясната част на лентата, което направихме същото, но в обратен ред (най-маловажния бит в главата). В този случай, добавянето или заличаването на знака на главата съответства на аритметична операция (отстраняване на това число деление, умножение чрез добавяне на корен и добавяне). С този ход кодиране функция (четирите функции на четирите аргументи, показващи следващото състояние, като функция на предишния), написана от прости формули и са примитивно рекурсивни.
А сега да разгледаме итерирания функция преход, който казва какво ще бъде състоянието на машината на Тюринг, след т стъпки. По-точно, има четири функции на петте аргументи (първите четири аргументи са кодирани състояние, петата е броя на стъпките). Тяхното определение е дадено от съвместната рекурсия, която току-що взети от друг. Следователно, тези функции са примитивни рекурсивно. Предполагаме, че след появата на окончателния статут на конфигурацията на машината не се променя. Ако знаем, че броят на работните стъпки се ограничава до примитивно рекурсивни функции. достатъчно е да го замества на мястото на петия аргумент (брой стъпки), за да се гарантира, че крайната конфигурация на машината е примитивно рекурсивни функция на първоначалната си конфигурация. Следователно, на изхода на примитивни рекурсивни функции първоначалните данни.
Този аргумент имплицитно използва примитивни recursiveness различни функции, свързани с прехода от една оглед другите данни. Така например, на входа на машината на Тюринг е двоична дума, че сме се съгласили да бъдат идентифицирани с определен брой х. Този пост съответства на първоначалната конфигурация на машината на Тюринг, която ние код от четири цифри. Важно е, че тези четири примитивен рекурсивно зависи от х. Лесно е да се разбере, защото преобразуването, свързано с преминаването от един номер система към друга (една и съща дума кодира различни числа в различни бройни системи); примитивен recursivity такива функции лесно инсталирани използвайки методите, описани по-горе. Освен това, ние се нуждаем от изхода конфигурацията на примитивно рекурсивни възстановяване на резултата, а също и повторно кодиране него и ще го кача на дължината вход (да замени в примитивно рекурсивни функции, ограничаване на броя на стъпките). Но всичко това също не е извън обхвата на техники обсъдени по-горе, както и да се спирам на това, ние няма.
Тази теорема ни показва примитивни рекурсивни много доста трудно определими функции. Например, да разгледаме функция М (п Th десетично число). Известно е, че изчислява на милиони такива признаци, така че има всички основания да вярваме, че някои алгоритми работа не е твърде дълго ще са много странни, ако по време на тяхната работа (дори и с неудобството на машина на Тюринг за програмиране) да бъде направена оценка, например, функцията CX 2 п за достатъчно голям С. И тази оценка е примитивно рекурсивни, което позволява да се отнася до малко над теорема. (Всъщност, съществува голям запас от примитивни рекурсивни функции., Които растат много по-бързо от 2 п.)
Друго описание на класа на примитивни рекурсивни функции. повече програмист приятелски: тя функции, които могат да изчисляват програма, включваща ако-то-друг и -vetvleniya за -cycles, но не съдържат докато -cycles (а оттам и отиват в пакости и различни други видове промени за- цикъл в рамките на параметъра на верига) ,
87. членка и да докажат съответния отчет.
Частични рекурсивни функции
Операторите примитивна рекурсия и заместване не ни водят от клас навсякъде дефинирани функции. Не е така с минимизиране на оператора. които вече споменахме. Той се прилага за (к + 1) -place функции Е и Ж дава функция к-ка. определя, както следва: г (. x1 XK) е най-малката ш. за които е (х1. XK, у) = 0.
Смисълът на избраната дума е ясно, ако функцията F се определя навсякъде. Ако не, те трябва да се разбира както следва: стойността на г (X1 XK.) Равна на у. ако е (х1. XK, у) се определя и е равна на нула, и всички стойности на F (х1. YK, у ') с Y' Често се използва обозначение и по тази причина се минимизира оператор-оператор се нарича още. Ясно е, че такова определение осигурява изчислимост гр. ако изчислим е (ние сортиране във възходящ ред всички у. в очакване на стойност нула). 88. показват, че ако определянето на климата и позволява е (х1. Xk, у ') да бъдат определени при Y' Функции, получени от основния (нула, единица проекция и добавяне) от оператора на заместване, примитивен рекурсията и минимизиране, наречен частично рекурсивно. Ако тази функция е навсякъде дефиниран, а след това той се нарича рекурсивна функция. Тази странна терминология очевидно образувани в резултат на преводи от английски език. На английски език са "примитивни рекурсивни функции" (примитивни рекурсивни функции). След това бе дадена по-общ (общо) концепция навсякъде определено изчислимите функции и такива функции са били наречени "общи рекурсивни функции". Тогава помисли за стомана и частични (частично) изчислимите функции, наричайки ги "частични рекурсивни функции". на български език, думата "частично" сбъркали мястото и вместо частични рекурсивни функции започнаха да говорят за частични рекурсивни функции. Същата съдба сполетява думата "генерал", която е странно влезе прилагателното "повтаряща се" и показва, че функцията е дефинирана навсякъде. Теорема 76. Всяка функция. изчислимо от машина Тюринг е частично рекурсивно. Нека е да бъде изчислимо от машина Тюринг (означават тази кола чрез М) функция на един аргумент. Да разгледаме собственост Т (х, у, т). състоящ се в това, че машината м вход х у дава отговора по време на не повече от т. Както видяхме по-горе, на входа на машината на Тюринг и време тон може да бъде примитивно рекурсивно изчисляване на неговото състояние в момента тон; ясно е, че също така е възможно, за да разберете дали той е приключил, и ако е така, дали отговорът е равно на х. По този начин, Т е примитивен рекурсивен собственост. Сега се комбинират аргументи у и т в двойката чрез примитивен рекурсивен изброяване; превърне примитивно рекурсивни функции T '. за което Т '(х, [Y, п]) = Т (х, у, т); Сега можем да пиша, където p1 дава броят на двойките през първия мандат, което означава "най-малко на Z. За това.". Така, функцията F е частично рекурсивно. Обратното също притежава Теорема 77. Всеки частичен рекурсивни функция е изчислима от машина на Тюринг. Лесно е да се напише програма, с краен брой променливи, изчисляване на всяко частично рекурсивна функция (смяна намалява последователното прилагане на програми, като рекурсия за цикъл за известно време минимизиране тип цикъл. И двата вида цикли могат да бъдат внедрени лесно с помощта на преход оператори). След това остава само да се позова на факта, че всяка функция. изчислява чрез програмата, с ограничен брой регистри, е изчислима от машина на Тюринг (както видяхме в раздел 10.2, Теорема 66). Ето защо, ако ние вярваме в "Тюринг теза", който гласи, че всеки изчислима функция е изчислима от машина на Тюринг, трябва да вярваме в "тезата Чърч" (всеки изчислима функция е частично рекурсивно), така че тези точки са еквивалентни. Всъщност, историята е по-сложно и може да се опише по следния начин грубо. Определяне на примитивно рекурсивни функция е дадена голяма логик Курт Гьодел и се използва като технически инструмент за доказване на непълноти теорема на Гьодел, в началото на 1930-те години. Той даде определението на рекурсивни функция (не съвпада с тази, дадена от нас, а негов еквивалент). Американската логик Алонсо Чърч формулира тезата си за навсякъде определени функции. приемайки, че всяка изчислимо навсякъде дефинирана функция е рекурсивно. След това, на американския математик Kleene предлага да се разшири този аргумент за функции, които не са дефинирани навсякъде. Успоредно с това, английски математик Тюринг и американският математик Мнение предлагат модела на абстрактни компютри (Тюринг машини и пост), които се различават само в някои детайли, и предполага, че тези машини покриват целия клас на алгоритмични процеси. Скоро стана ясно, че изчислима функция на тези машини е еквивалентен на частичен рекурсивно. (Исторически данни могат да се научат от книгата на Kleene [4]). Както и да е, днес терминът "Тюринг теза", "Църква теза", "теза заговезни" и т.н. обикновено се използват като синоними: тезисите твърдят, че интуитивно разбира класа на изчислимите частични функции съвпада с официалната дефиниция на класа на частични рекурсивни функции (Църква теза) изчислима от Машина на Тюринг функции (Тюринг теза), и т.н. С това разбиране, ние може да докаже еквивалентността на тези резюмета, тъй като всички известни официално определения изчислимост (частични рекурсивно Тюринг машини и т.н.) водят до един и същи клас на функции. (Трябва да отбележим мимоходом, че друг изчислителни модели на нормалните алгоритми. Или Марков алгоритми. Бяха предложени Андрей Андреевич Марков-младши (син на по-голямата, след което той нарича Марковски вериги и Марков процеси). Това беше през 1950. Марк е написал думата алгоритъм до "е". съответният принцип (всеки алгоритъм е еквивалентно на нормалното), той нарича принцип на нормализиране. в произведенията му, нормалните алгоритми, използвани за изграждане на непримирим асоциативен смятане. Освен това, Марков всъщност напишете л във всички подробности за универсален дизайн алгоритъм и е имал точно доказателство за неговата правилност, както изглежда, това постижение в никакъв случай не се повтаря никой друг не са имали постоянство, за да за някои език за програмиране да пишат на езика на неговия преводач и официално доказва своята коректност).Свързани статии