Рекурсивные функции
Содержание
Введение
------------------------------------------------------------------------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)>|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.