Читайте данную работу прямо на сайте или скачайте

Скачайте в формате документа WORD


Рекурсивные функции

Содержание

Введение ------------------------------------------------------------------------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.


Также я приведу определенные понятия рекурсивного предиката, как предиката, представляющая функция которого является рекурсивной. Таким образом, рекурсивные предикаты это в точности такие предикаты R W, для которых эффективно решается проблема вхождения, т. е. проблема определения по заданной n-ке чисел < m1,..., mn >.

Рекурсивные функции

Напомним, что под частичной функцией мы понимаем здесь, всякое,

отображение

f: X о w, где ХÍ wn для некоторого nÎх. Число п в этом, случае называется

местностью частичной функции fа и обозначается через v(f). Если

f: X оw - частичная функция, то будем называть f нигде не

определенной при X = Æ и всюду определенной при. X = wv(f)*). Всюду

определенную частичную функцию в дальнейшема будема называть

просто функцией. Частичную функцию местности п будем называть n-

местной частичной функцией. Мы допускаем случай, когда n = 0. Тогда 0-

местная функция f: 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:n X 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 называется рекурсивной.

В следующем параграфе будет доказано, что любая всюду определенная

частично рекурсивная функция является рекурсивной.

Из данного определения и приведенных выше замечаний о сохранении

вычислимости операторами S, R, М легко следует, что всякая частично

рекурсивная функция является вычислимой.

Обратное утверждение носит название тезиса Чёрча: любая вычислимая частичная частично рекурсивна.

Исторически именно это тверждение было первым точным математическим

определением понятия (алгоритмически) вычислимой функции.

Имеет место следующая теорема, доказательство которой мы опустим из-

за его громоздкости.

Теорема 2

Класс частично рекурсивных' функций совпадает с классом функций,

вычислимых, по Тьюрингу.

Таким образом, тезис Тьюринга эквивалентен.тезису Чёрча.

Пусть k, nÎw - некоторое отображение множества {1,...,k} в множество {1,...,n} fЧ k-местная частичная функция. Будем говорить, что n-местная частичная функция g получена из f подстановкой ее, если для любых m1,.., mnÎw имеет место соотношение:

g(m1,.., mn))=(ma1,..,mak).

Будем использовать в этом случае обозначение g=fa

Предложение 1.

Если f Ч частично рекурсивная функция и g получен из f подстановкой а, то g частично рекурсивна.


Доказательство 1.

Легко проверить, что если g=fa, то

g=Sn,k-1(f, I na1,Е,I nak)


Предложение 2.

Следующие функции рекурсивны:

1)Пулъместные функции n, nÎw;

2)двухместная функция сложения +;

3)двухместная функция множения Х ;

4)двухместная функция сеченной разности Х, определенная следующим

образом:

5)одноместные функции sg и sg, определенные следующим образом:


двухместная функция идентификации 6, определенная следующим образом:

Доказательство 2.

Покажем рекурсивность нуль - местной функции {< Æ, n>} индукцией по n. Функция {< Æ, 0>}а равна M(0). Если функция {< Æ, n>} рекурсивна, то рекурсивна функция S{< Æ, n>}={< Æ, n+1>}. Так как n+0 = n и n+(m+1) то функция + равн R(I11 S(I33)). Из равенств nХ0=0 и nХ(m+1) =

nХm+n следует, что функция равна R(0,I11 +I33)

Для того чтобы показать рекурсивность Ч усеченной
разности рассмотрим одноместную функцию -- 1 определённую так:

Она равн R(0, I21)а поэтому рекурсивна. Так как n - (m+1)=(n - m) - 1, то функция -- равна R (I11, I33 - 1) следовательно, также является рекурсивной.

Рекурсивность функций следует из равенств sg = R(o,s (0(I21))) и sg=R(1,0(I21)). Пусть a:{1,2} о {1,2}такого что a(1=2), a(2=1), a fЧ функция

полученная из функции -- подстановкойа а. Тогда для функции δ

справедливо равенство δ=S(sg), S(+,--,f)). Из рекурсивности функций sg - и предложения получаем, что функция идентификации δ является рекурсивной.

Для задания, рекурсивныха функций и изучения их свойства удобно-

пользоваться специальныма формальным языком Rå.

Пусть V={Ui I iÎw} - множество переменных, элементы лоторого

будем обозначать буквами х, у, z, w, и, возможно с индексами.

Пусть å(R,F,M) - некоторая конечная сигнатура такая, что

FÊ F0={0,s,+,Х) где 0 символ нульместной функции, sа Ча символ одноместной функции, +, Х - символы двухместных функций;а RÊR0 ={<}, где < символ двухместного предиката.

Определение выражений, (синтаксис) языка Råабудет зависеть еще и от семантики этого языка. Поэтому определение синтаксиса и семантики будет вестись, одновременно, но прежде всего зададимся фиксированной алгебраической системой Wåасигнатуры åас основным множеством w и такой, что значения символов сигнатуры å0 = (R0,F0,Mn) совпадают с функциями и предикатом, обозначенными этими символами ранее (например, символу Х соответствует операция множения натуральных чисел).

Итак, будем одновременной индукцией определять понятие å-терма, å-формулы (более точно было бы говорить об Wåатермах и Wå-формулах), множества свободных переменных FV(t) и FV(j) å-терма t и å-формулы j соответственно, натуральное число t[h] и истиостное значение j[h]Î{и,л} для всякой интерпретацииоw где ХÍV,FV(t) FV(j)ÍX;

) символ 0 является å-термом, FV(0=Æ) и 0[h=0];

б)переменная хÎу является å-термом, FV(x)={x}, x[h]=h(x);

в)если fÎF - n-местный функциональный символ, t1,Е,tn å-термы; то

å-терм f(f1,...,tn); FV(f(t1,Е,tn))=FV(t1)UЕU FV(tn); F(t1,Е,tn) [h]=fWå (t1[h],Е,tn[h])

здесь fWå-n местная операция Алгебраической системы Wå соответствующая сигнатурному символу f;

г) если (QЧ n-местный предикатный символ из Ra t1,Е,tn å-термы, то Q(t1,Е,tn) å-формула, FV(Q(t1,Е,tn))=FV(t1)UЕUFV(tn); Q(t1,Е,tn) [h] здесь QWåЧ n-местный предикат, соответствующий в алгебраической
системе Wå предикатному символу Q;
д)Если t1,Е,t2 å-термы, t1≈t2 å-формула, FV(t1≈t2) =FV(t1)UFV(t2), (t1≈t2) [h] = и <=> t1[h]=t2[h];

е)Если j и ψ å-формула то ┐j,(j,t,ψ) для tÎ{∧,∨,о} å-формулы, fV(┐j) = FV(j), FV(j,t,ψ)=FV(j) U FV(ψ) и (┐j)[h] = ┐(j[h]) где ┐ ∧,∨,о операции определены на множестве {и,л} таблицей (1) c заменой ло на л и л1 на ли

ж)Пусть j å-формула, xÎV и для любой интерпретации h1:Xоw для которой xÏX и FV(j)ÍXU{x} cсуществует такое же n, что j[h] = и для h=h1 U{<x,n>}; тогда m x j å-терм, FV(mxj) = FV(j) \ {x} и (mxj)[h] -наименьшее n0Îw для которого j[hТ]= и где hТ=(h \ {<x,hx>})U{<x,n0>} Индукцией по построению å-терма (å-формулы) Q легко станавливается, что для любыха интерпретаций h0:x0оw, h1:x1оw с таких, что FV(Q)Íx0 ∩ x1 аи для всех xÎFV(Q)h0 (x)= h1 (x) и для всех выполняется равенство Q[h0]= Q[h1].

Как обычно, в место +(t1,t2)Х(t1,t2)) будем писать (t1+t2)((tХt2)) и (t1<t2). Вместо <( t1,t2 ). Кроме того, будем пользоваться обычными

сокращениями для термов и формул, принятыми ва арифметике и

исчислении высказываний (например, вместо (x+((zХz)+(xХy))) и ((j∧ψ) оj будем писать соответственно x+z2а+xy и (j∧ψ) оj).

Для å-формулы j и интерпретации h; xоw FV(j)Íx, часто вместо j[h] = и будем писать j[h] истинно или просто j[h]. А вместо j[h] = ∧ будем писать j[h] ложно или л┐j[h].

ПустьQ - å-терм или (å-формула). Вхождение переменной x в Q называется свободным, если оно не находится в пол слове вид mxj являющемся å-термом. Если вхождение переменной в не является свободным, то оно называется связанным. Легко проверить, что множество FV(Q)а состоит в точности из переменных, имеющих свободные вхождениям в Q.

Пусть вQ å-терм (å-формула), x1,Е,xnÎVа - различные переменные, t1,Еtn å-терма такие, что для любого iÎ{1,Е,n} и любого yÎV(t1) ни одно свободное вхождение в Q переменной Xi не содержится в терме вид являющемся myj под словом Q.

абудет обозначать результат замены всех свободных вхождений переменных х1,..,хn н å-термы - t1,...,tn соответственно.

Ю. Л. Ершов, Е. Л. Палютиа

Индукцией по построению å-терма и å-формулы без труда станавливается следующее.

Предложение 3.

Если Q å-терм (å-формула) х1,..,хnÎV - различные переменные, t1,...,tn - å-термы такие, что для Q, х1,..,хn, t1,...,tn выполнены сформулированные выше словия, то

1) Q1=является å-тepм (å-формулой), в такойа для любой интерпретации h:xоw. В такой, что (FV(Q)\{х1,..,хn})UЕUFV(tn)Íx выполняется равенство Q1[h]=Q[h] где hТ = {<y,h(y)>|yÎFV (Q)}. Про å-
терм (å-формулу) будем говорить, что Q получен из Q подстановкой å-
термов t1,...,tn вместо переменных х1,..,хn.

К сожалению, словия для возможности подстановки å-термов вместо
переменных не всегда выполнены. Чтобы всегда иметь возможность для
подстановки, введем следующие понятия. Будем говорить, что å-терм (å-
формула) Q получается из å-терма (å-формулы) Q, заменой связанной
переменной, если Q получается из заменой вхождения å-терма mxj на my(j)xy где yÎFV(j). å-термы (å-формулы) Q и Q1 называются конгруэнтными, если существует такая последовательность Q0,Е,Qnа что Qo = Q1 ; Qo = QТ; QI+1,I<n, получается из Q заменой связанной переменной. Очевидно, что отношение конгруэнтности является эквивалентностью на множестве å-термов и å-формул.

Предложение 4.


Если Q и Q' - конгруэнтные å-тёрмы или å-формулы, то FV(Q=FV(QТ)) для любой интерпретации h:FV(Q)оw имеем Q[h]=QТ[h].




Доказательство 3.

Индукцией по длине Q легко показать, что если Q1 получается из Q заменой связан ной переменной, то тверждение предложения истинно. Далее индукция по длине последовательности Q0,Е,Qn из предыдущего определения.

Отметим, что для любого å-терма ( å-формулы) Q, любого набора попарно различных переменных x1,Е,хn любых å-термова t1,...,tn существует å-терм (å-формула) Q' такой (такая), что Q' конгруэнтен (конгруэнтна) Q и для Q' выполнены словия для подстановки апользуясь этим свойством и предложением 4, будем впредь использовать запись , не заботясь о выполнении словий на связанные переменные считая, что если эти словия не выполнены, то аесть адля å-терма (å-формулы) Q', конгруэнтного (конгруэнтной) Q в, причём для Q' все словия для подстановки же выполнены.

Напомним, что подмножество XÍAn называется n-местным предикатом на А. В дальнейшем под предикатами будем понимать предикаты на w. Если n-местный предикат, то n-местная функция nx определенная следующим образом: для любых m1,Е,mnÎw случаев,

называется представляющей функцией для X. Наряду с представляющей функцией px предиката X часто используют характеристическую функцию Xх предиката X, которая связана с функцией px соотношением Xx= sg(px) предикат X называется рекурсивным, если его пред ставляющая функция px рекурсивна.

лгебраическая система Wå называется рекурсивной, если все функции и предикаты, соответствующие символам сигнатуры å, являются рекурсивными.

В дальнейшем, говоря о å-формулах и å-термах (определение которых
зависит от фиксированной алгебраической системы Wå, будем всегда
предполагать, что Wå - рекурсивная алгебраическая система.
Заметим, что предикаты ≈,< являются рекурсивными, так как

представляющей функцией для ≈ является функция идентификации δ представляющей функцией для < будет рекурсивная функция sg(S(I21) - I22). С каждым å-термом ( åа-формулой) можно связать

семейство функций (предикатов), которые реализуются
этим å-термом ( å-формулой). Для обозначения этих

функций (предикатов) будем использовать расширение языка, Råадобавив новую пару [,] символов квадратных, скобок.

Перейдем к точным, определениям.

Если t- å-терм для i¹j то через t[x1,Е,хn] будем обозначать n-местную функцию, принимающую н n-ке <m1,Е,mn> значение t[h], где h={<x1,m1>│I=1,Е,n}. Если j - å-формулой и FV(j)Í{x1,Е,хn}Í, x1¹xj, для i¹j, то через будем обозначать предикат {<m1,Е,mn>│j[h]={<xi,mi>│I=1,Е,h}}. Заметим, что один и тот же å-герм

+ реализует много функций, например, если FV(t)Í{x,y} то [x,y], +[y,x] и [x,y,z], вообще говоря, различные функции символ [x1,Е,хn] играет роль, аналогичную кванторам, он связывает x1,Е,хn так, например, если FV(t)Í{x1,Е,хn} и y1,Е,yn попарно различные переменные, то имеета место равенство.

t[x1,Е,хn] = а[ y1,Е,yn].

Заключение

В этой курсовой было определено понятие рекурсивного предиката, как предиката, представляющая функция которого является рекурсивной. Таким образом, рекурсивные предикаты это в точности такие предикаты R W, для которых эффективно решается проблема вхождения, т. е. проблема определения по заданной n-ке чисел <m1,..., mn>.

Так же рассмотрели частично рекурсивные функции совпадающие с классом функций, вычислимых, по Тьюрингу.

В этом реферате мы привели способ точнения понятия вычислимой функции который можно назвать алгебраическим, так как определяемый класс функций будет порождаться из некоторых простейших функций с помощью некоторых операций. Под частичной функцией мы понимаем f: X о w, где ХÍ wn для некоторого nÎх.

Спасибо за то что прочитали эту курсовую, надеюсь вы почерпнули из прочитанного материала много нового и познавательного.

Список Литературы

1.     Марченко С.С. Элементарные рекурсивные функции. М.: МЦНМО, 2003.

2.     Кузнецов А.В. К теореме о канонической форме для ординально-рекурсивных функций. В книге Гудстейн Р. Л. Математическая логика. М.: ИЛ, 1961, с. 149-154.

3.     Смальян Р. Теория формальных систем. М.: Наука, 1981.

4.     Косовский Н. К. Элементы математической логики и ее приложения к теории субрекурсивных алгоритмов. Л., Из-во Ленинград. н-та, 1981.

5.     Гжегорчик А. Некоторые классы рекурсивных функций. В книге: Проблемы математической логики. М., Мир, 1970, с. 9-49.