Содержание
Введение------------------------------------------------------------------------2
Рекурсивные функции------------------------------------------------------------------3
Определение-----------------------------------------------------------------------------4Теорема 2.--------------------------------------------------------------------5
Предложение1. -------------------------------------------------------------------------5Доказательство 1. --------------------------------------------------5
Предложение2. --------------------------------------------------------------------------5Доказательство 2.------------------------------------------------------6
Предложение 3. -------------------------------------------------------------------------------------------------------8
Предложение4.-----------------------------------------------------------------------------9
Доказательство 3.---------------------------------------------------------------------9
Заключение -------------------------------------------------------------------------------------------11Список Литературы--------------------------------------------------------------------12
Введение
В этом реферате мы приведем способ уточнения понятиявычислимой функции который можно назвать алгебраическим, так как определяемыйкласс функций будет порождаться из некоторых простейших функций с помощьюнекоторых операций. Под частичнойфункцией мы понимаемf: X®w,где ХÍwnдля некоторого nÎх.
Так же рассмотрим частичнорекурсивные функции совпадающие с классом функций, вычислимых, по Тьюрингу.
Ниже приведёммножество примеров и доказательств этой теоремы таких как:
g=Sn,k-1(f, I na1,…,I nak)
ипредложения как на пример:
1)Пулъместныефункции n, nÎw;
2)двухместнаяфункция сложения +;
3)двухместнаяфункция умножения • ;
4)двухместная функция усеченнойразности •,
___
5)одноместныефункции sgи sg,
6)двухместная функция идентификации 6.
Также я приведу определенные понятия рекурсивногопредиката, как предиката, представляющая функция которого является рекурсивной.Таким образом, рекурсивные предикаты это в точности такие предикаты RW, для которых эффективно решаетсяпроблема вхождения, т. е. проблема определения по заданной n-ке чисел .
Рекурсивные функции
Напомним, что подчастичной функцией мы понимаем здесь, всякое,
отображение
f: X ® w, где ХÍ wn для некоторого nÎх. Число п в этом, случае называется
местностью частичной функции f и обозначается через v(f). Если
f: X ®w — частичная функция, то будем называть f нигде не
определенной при X = Æ и всюду определенной при. X = wv(f)*). Всюду
определенную частичную функцию в дальнейшем будем называть
просто функцией.Частичную функцию местности п будем называть n-
местной частичнойфункцией. Мы допускаем случай, когда n = 0. Тогда 0-
местная функция f: w°® w будетсостоять из одной пары , п> для
некоторого nÎw и часто будет отождествляться с числом n. Всюду в даль-
нейшем буквы т, k, n, I и j ], возможнос индексами, будут обозначать
натуральные числа.
Пусть f: X ®w— n-местнаячастичная функция. Если m1,.., mл>ÎX, то f(m1,..,mл) — это значение функции f на п – ке m1,..,mл>. Если m1,..,mл>ÏX, то будем говорить, что f(m1,..,mn) не определено или что f не определена на n-ке m1,..,mn >. Ясно, что для задания частичной n-местной функции достаточно для любой n-ки m1,..,mn> сказать, определеноли f(m1,..,mn) и если определено, то указать число k = f (m1,..,mn). Если f и g— частичные функции, то будем писать f(m1,..,mn)=g(m1,..,mn)
когда обе части равенства определены и равны, либо обе части
равенства неопределены.
Пусть семейство всех n — местных частичныхфункций, а = U n,семейство всех частичных функции.
Определим насемействе всех частичных функций операторы S, R, М, которые сохраняютвычислимость функций.
Пусть n, kÎw, f—(n+1)-местнаячастичная функция, go,..., gn — k-
местные частичные функции. Определим k-местную частичную функцию h
следующим образом: h(m1,.., mk) не определено, если хотя бы одна из
частичных функций go,..., gn не определена на _ m1,..,mk > и если
все go,...,gn определены на m1,..,mk>, то h(m1,..,mk)=f(go(m1,..,mk)…, gn(m1,.., mk)).
Будем говорить,что h полученарегулярной суперпозицией из f, g0, …, gn и обозначать это следующим образом h=Sk,n(f, g0, …, gn). Оператор (регулярной суперпозиции)- Sk,n является всюду определенным отображением из n+1 X n+1 k в k и сохраняет вычислимость, т.е. если частичные функции f Î n+1; g0, …, gn Î k вычислимы,то и частичная функцияSk,n (f, g0, …, gn) вычислима. Верхние индексы, у оператора S будут опускаться ивместо S(f, g0, …, gn) будет, как правило, использоваться более привычное, но менее точное обозначение f(g0,..., gn). Пусть n Îw,fÎn,gÎn+2.Определим по f и g (n + 1) — местную частичную функцию h так, что для любых m1,..,mn Îw
h(m1,.., mn,0)=f(m1,.., mn);
h(m1,..,mn,k+1)не определено, если h(m1,..,mn, k) не определено и h(m1,..,mn, k+1) = g(m1,..,mn,k), h(m1,..,mn,k)), если h(m1,.., mn, k) определено. Очевидно, что h однозначно определена по f и g и вычислима, если вычислимы / и указанное определение h по / и g задает оператор h=R n+1:nX n+2 ®n+1 который назовем оператором примитивной рекурсии. Про h=функцию h = R n+1(f, g) будем говорить, что она получила примитивной рекурсией из функций f иg. Верхний индекс у оператора Rn+1 будем опускать.
Пусть nÎw,fÎn+1. Определим по f такую n-местную частичную
функцию g, что для любых k, m1,..,mn Îw тогда и только тогда,когда f(m1,..,mn,0)=0и k=0или k>0и f(m1,..,mn,0)определены и неравны нулю, а f(m1,..,mn,k)=0. Ясно, что такая функция д существует и однозначно определена по f;кроме того, если f — вычислимая функция, то из определения g видно, как вычислять g. Таким образом, задан оператор M n — оператор минимизации — из n+1в nесли g= M n (f) то будем говорить, что g получена минимизацией из f .
Базиснымифункциями называются функции о, s, I nm (1≤m≤n) где о —
одноместнаяфункция, которая па любом n принимает значение 0, s — одноместная функция, принимающая на числе n значение n+1, a I nm — n-местнаяфункция, принимающая на наборе (k1,…,kn) значение km. Очевидно, что базисные функции вычислимы.
Определение.
Частичнаяфункция fназывается частично рекурсивной,
еслисуществует такая конечная последовательность частичных функций
g0, …, gk что gk=f икаждая g i, i≤k либо базисная, либо получается из
некоторыхпредыдущих регулярной суперпозицией, примитивной рекурсией
или минимизацией. Эта последовательность g0, …,gk называется определяющей последовательностью для f. Если для всюду определенной
частично рекурсивной функции f существует определяющая
последовательность,состоящая только из всюду определенных функций, то f называется рекурсивной.
Вследующем параграфе будет доказано, что любая всюду о