Рекурсивные функции
Содержание
Введение
------------------------------------------------------------------------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°® 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)((t1•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)>. Про å-
терм (å-формулу) будем говорить, что 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.