Кіріспе
Есептеуге қабілеттілік теориясындағы теорема. Есептеуге қабілеттілік теориясында Клейннің рекурсия теоремалары – есептеу функцияларын өздерінің сипаттамаларына қолдануға қатысты маңызды екі теорема. Бұл теоремалар алғаш рет 1938 жылы Стивен Клин тарапынан дәлелденген және 1952 жылы жарық көрген «Метаматематикаға кіріспе» кітабында жарияланған. Есептелетін функцияның тұрақты нүктесін құрастыратын ұқсас теорема Роджерс теоремасы деп аталады, және оның авторы – Хартли Роджерс кіші. Рекурсия теоремаларын есептеу функцияларындағы белгілі бір операциялардың тұрақты нүктелерін құруға, квиндерді жасауға және рекурсивті анықтамалар арқылы анықталатын функцияларды құруға қолдануға болады.
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr. The recursion theorems can be applied to construct fixed points of certain operations on computable functions, to generate quines, and to construct functions defined via recursive definitions.
Нөмірлік
Теоремалардың тұжырымы ішінара рекурсивті функциялардың қабылданатын нөмірленуіне сілтеме жасайды, онда индекске сәйкес келетін функция егер және табиғи сандардағы ішінара функциялар болса, онда әрбір n үшін, не екеуі де анықталған және тең, не болмаса екеуі де анықталмаған болады.
If and are partial functions on the natural numbers, the notation indicates that, for each n, either and are both defined and are equal, or else and are both undefined.
Роджерстің тұрақты нүкте теоремасы
Берілген функция , -ның тұрақты нүктесі – бұл индекс , осындай болғандағы . Ескеріңіз, және шығыстардың салыстырылуы сандық мәндер бойынша емес, олармен байланысты функциялар бойынша жүзеге асырылады. Роджерс бұл нәтижені Клиннің (екінші) рекурсия теоремасының "жеңілдетілген нұсқасы" деп сипаттайды.
Белгілі нүкте теоремасының дәлелі
Дәлелдеуде келесідей анықталған белгілі бір толық есептелетін функция қолданылады. Берілген натурал сан *n*, функция *f(n)*, келесі есептеуді орындайтын ішінара есептелетін функцияның индексін шығарады: берілген кіріс *x* үшін, алдымен *f(x)* есептеуді бастаңыз. Егер бұл есептеу нәтиже берсе, онда *g(f(x))* есептеуді орындап, нәтижесін қайтарыңыз, егер ол болса. Осылайша, барлық ішінара есептелетін функциялардың индекстері үшін, егер *g(f(x))* анықталса, онда *f(x)* анықталған. Егер *g(f(x))* анықталмаса, онда *f(x)* ешқайда анықталмаған функция болады. *f(n)* функциясын жоғарыда сипатталған ішінара есептелетін функциядан және s m n теоремасынан құрастыруға болады: әр *n* үшін, *f(n)* функциясын есептейтін бағдарламаның индексі болып табылады. Дәлелді аяқтау үшін, *h* кез келген толық есептелетін функция болсын, және *f(n)* функциясын жоғарыда көрсетілгендей құрастырыңыз. *h(f(x))* композициясының индексі *i* болсын, ол толық есептелетін функция. Онда, *i* анықтама бойынша *h* индексі, яғни *i = h*. Бірақ, *h* функциясы *f(x)* индексі болғандықтан, *h = f(x)*, және осылайша *i = f(x)*. Транзитивтілік қағидасы бойынша, бұл *f(x) = f(f(x))* дегенді білдіреді, сондықтан *f(x)* үшін *f(f(x))* орындалады. Осылайша, бұл дәлел Y комбинаторын іске асыратын ішінара рекурсивті функцияның құрылысы болып табылады.
Given an input , first attempt to compute If that computation returns an output , then compute and return its value, if any. Thus, for all indices of partial computable functions, if is defined, then If is not defined, then is a function that is nowhere defined. The function can be constructed from the partial computable function described above and the s m n theorem: for each , is the index of a program which computes the function
To complete the proof, let be any total computable function, and construct as above. Let be an index of the composition , which is a total computable function. Then by the definition of But, because is an index of , , and thus By the transitivity of , this means Hence for
This proof is a construction of a partial recursive function which implements the Y combinator.
Белгілі нүктесіз функциялар
Барлық мән үшін функция тұрақты нүктесіз деп аталады. Тұрақты нүкте теоремасы ешбір толық есептелетін функция тұрақты нүктесіз бола алмайтынын көрсетеді, бірақ есептелмейтін тұрақты нүктесіз функциялар көптеген. Арслановтың толықтық критерийі бойынша, тұрақты нүктесіз функцияны есептейтін жалғыз рекурсивті санамалы Тьюринг дәрежесі – 0′, тоқтау мәселесінің дәрежесі.
Роджерс теоремасымен салыстыру
Клиннің екінші рекурсия теоремасы мен Роджерс теоремасын бір-бірінен салыстырмалы түрде оңай дәлелдеуге болады. Дегенмен, Клин теоремасын тікелей дәлелдеуде әмбебап бағдарлама қолданылмайды, демек теорема әмбебап бағдарламасы жоқ кейбір субрекурсивті бағдарламалау жүйелері үшін де қолданылады.
Рефлексивті бағдарламалау
Рефлексивті немесе рефлективті бағдарламалау – бағдарламаларда өзіне-өз сілтеме жасауды қолдануды білдіреді. Джонс рефлексивті тілге негізделген екінші рекурсия теоремасын қарастырады. Рефлексивті тілдің рефлексиясыз тілден артық еместігі көрсетілді (өйткені рефлексивті тілдің интерпретаторы рефлексияны қолданбай-ақ жүзеге асырылуы мүмкін); содан кейін рекурсия теоремасы рефлексивті тілде өте оңай екендігі көрсетілді.
Мысал
Екінші рекурсиялық теорема сияқты, бірінші рекурсиялық теореманы рекурсиялық теңдеулер жүйесін қанағаттандыратын функцияларды алу үшін қолдануға болады. Бірінші рекурсиялық теореманы қолдану үшін рекурсиялық теңдеулерді алдымен рекурсивті оператор ретінде қайта құру керек. Факториалдық функция f үшін рекурсиялық теңдеулерді қарастырайық: Сәйкес рекурсивті оператор Φ алдыңғы мәннен f-тің келесі мәніне қалай жету керектігін көрсететін ақпаратқа ие болады. Алайда, рекурсивті оператор f графигін анықтайды. Бірінші кезде, Φ жұпты қамтиды. Бұл f(0) = 1 екенін нақты көрсетеді, сондықтан (0,1) жұбы f графигінде болады.
Кейін, әр n және m үшін Φ жұпты қамтиды. Бұл егер f(n) = m болса, онда f(n + 1) = (n + 1)m, яғни (n + 1, (n + 1)m) жұбы f графигінде болады. Бастапқы жағдай 1 = f(0) = 1 болғанымен, рекурсивті оператор f(n + 1) мәнін анықтамас бұрын f(n) туралы ақпаратты қажет етеді. Бірінші рекурсиялық теорема (әсіресе, 1-бөлімі) F жиыны бар екенін айтады, яғни Φ(F) = F. F жиыны толығымен табиғи сандардың реттелген жұптарынан тұрады және қалағандай, f факториалдық функциясының графигі болады. Рекурсивті оператор ретінде қайта құрастырылатын рекурсиялық теңдеулерге шектеу рекурсиялық теңдеулердің шын мәнінде ең аз тұрақты нүктені анықтайтынын қамтамасыз етеді. Мысалы, рекурсиялық теңдеулер жиынтығын қарастырайық: Мұндай теңдеулерді қанағаттандыратын g функциясы жоқ, өйткені олар g(2) = 1 және g(2) = 0 екенін білдіреді. Осылайша, осы рекурсиялық теңдеулерді қанағаттандыратын g тұрақты нүктесі жоқ. Бұл теңдеулерге сәйкес келетін санау операторын жасауға болады, бірақ ол рекурсивті оператор болмайды.
Бірінші рекурсиялық теореманың дәлелдік сызбасы
Бірінші рекурсиялық теореманың 1-бөлігінің дәлелі бос жиыннан басталатын Φ санау операторын итерациялау арқылы алынады. Біріншіден, Fk тізбегі құрастырылады, яғни F0 бос жиын болсын. Индуктивті түрде, әр k үшін Fk+1 анықталады, содан кейін F деп қабылданады. Дәлелдің қалған бөлігі F-тің рекурсивті түрде саналатынын және Φ-ның ең кіші тұрақты нүктесі екенін тексеруден тұрады. Осы дәлелде қолданылған Fk тізбегі Клейне тұрақты нүкте теоремасының дәлеліндегі Клейне тізбегімен сәйкес келеді. Бірінші рекурсиялық теореманың екінші бөлігі бірінші бөліктен шығады. Φ рекурсивті оператор деген болжам, Φ-ның тұрақты нүктесінің ішінара функцияның графигі екенін көрсету үшін қолданылады. Басты мәселе – егер F тұрақты нүктесі функцияның графигі болмаса, онда Fk функцияның графигі емес, мұндай k табылады.
Екінші рекурсиялық теоремамен салыстыру
Екінші рекурсия теоремасымен салыстырғанда, бірінші рекурсия теоремасы күштірек қорытынды береді, бірақ бұл тек тар шешімдер орындалған жағдайда ғана мүмкін. Роджерс бірінші рекурсия теоремасын әлсіз рекурсия теоремасы деп, ал екінші рекурсия теоремасын күшті рекурсия теоремасы деп атайды. Бірінші және екінші рекурсия теоремаларының арасындағы бір айырмашылық – бірінші рекурсия теоремасы арқылы алынған бекітілген нүктелердің ең кіші бекітілген нүктелер екендігі кепілдендіріледі, ал екінші рекурсия теоремасынан алынғандары ең кіші бекітілген нүктелер болмауы мүмкін. Екінші айырмашылық – бірінші рекурсия теоремасы тек рекурсивті операторлар түрінде жаңадан құрастырылатын теңдеулер жүйелеріне ғана қолданылады. Бұл шектеу тәртіп теориясының Клейне бекітілген нүкте теоремасындағы үздіксіз операторларға қойылған шектеуге ұқсас. Екінші рекурсия теоремасын кез келген толық рекурсивті функцияға қолдануға болады.