Рекурсивные функции
Формат: doc
Дата создания: 22.02.2004
Размер: 55.01 KB
Скачать рефератСодержание
Введение ------------------------------------------------------------------------2
Рекурсивные функции ------------------------------------------------------------------3
Определение -----------------------------------------------------------------------------4
Теорема 2. --------------------------------------------------------------------5
Предложение 1. -------------------------------------------------------------------------5
Доказательство 1. --------------------------------------------------5
Предложение 2. --------------------------------------------------------------------------5
Доказательство 2. ------------------------------------------------------6
Предложение 3. -------------------------------------------------------------------------------------------------------8
Предложение 4. -----------------------------------------------------------------------------9
Доказательство 3. ---------------------------------------------------------------------9
Заключение -------------------------------------------------------------------------------------------11
Список Литературы --------------------------------------------------------------------12
Введение
В этом реферате мы приведем способ уточнения понятия вычислимой функции который можно назвать алгебраическим, так как определяемый класс функций будет порождаться из некоторых простейших функций с помощью некоторых операций. Под частичной функцией мы понимаемf: Xw, где Хwn для некоторого nх.
Так же рассмотрим частично рекурсивные функции совпадающие с классом функций, вычислимых, по Тьюрингу.
Ниже приведём множество примеров и доказательств этой теоремы таких как:
g=Sn,k-1(f, I na1,…,I nak)
и предложения как на пример:
1)Пулъместные функции n, nw;
2)двухместная функция сложения +;
3)двухместная функция умножения • ;
4)двухместная функция усеченной разности •,
___
5)одноместные функции sg и sg,
6)двухместная функция идентификации 6.
Также я приведу определенные понятия рекурсивного предиката, как предиката, представляющая функция которого является рекурсивной. Таким образом, рекурсивные предикаты это в точности такие предикаты R W, для которых эффективно решается проблема вхождения, т. е. проблема определения по заданной n-ке чисел < m1,..., mn >.
Рекурсивные функции
Напомним, что под частичной функцией мы понимаем здесь, всякое,
отображение
f: Xw, где Хwn для некоторого nх. Число п в этом, случае называется
местностью частичной функции f и обозначается через v(f). Если
f: Xw — частичная функция, то будем называть f нигде не
определенной при X = и всюду определенной при. X = wv(f)*). Всюду
определенную частичную функцию в дальнейшем будем называть
просто функцией. Частичную функцию местности п будем называть n-
местной частичной функцией. Мы допускаем случай, когда n = 0. Тогда 0-
местная функция f: w°w будет состоять из одной пары <, п> для
некоторого nw и часто будет отождествляться с числом 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, kw, 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+1k в k и сохраняет вычислимость, т.е. если частичные функции f n+1;g0, …, gn kвычислимы, то и частичная функция Sk,n (f,g0, …, gn) вычислима. Верхние индексы, у оператора S будут опускаться и вместо S(f, g0, …, gn) будет, как правило, использоваться более привычное, но менее точное обозначение f(g0,...,gn). Пусть nw,f n,g n+2.Определим по f и g(n + 1) - местную частичную функцию h так, что для любых m1,.., mnw
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=Rn+1: n X n+2 n+1 который назовем оператором примитивной рекурсии. Про h=функцию h = Rn+1(f, g) будем говорить, что она получила примитивной рекурсией из функций f и g. Верхний индекс у оператора Rn+1 будем опускать.
Пусть nw,f n+1. Определим по f такую n-местную частичную
функцию g, что для любых k, m1,.., mnw тогда и только тогда, когда f(m1,.., mn,0)=0 и k=0 или k>0 и f(m1,.., mn,0) определены и не равны нулю, а f(m1,.., mn,k)=0. Ясно, что такая функция д существует и однозначно определена по f; кроме того, если f — вычислимая функция, то из определения g видно, как вычислять g. Таким образом, задан оператор Mn — оператор минимизации — из n+1 в n если g= Mn (f) то будем говорить, что g получена минимизацией из f .
Базисными функциями называются функции о, s, Inm (1≤m≤n) где о —
одноместная функция, которая па любом n принимает значение 0, s — одноместная функция, принимающая на числе n значение n+1, aInm — n-местная функция, принимающая на наборе (k1,…,kn) значение km. Очевидно, что базисные функции вычислимы.
Определение.
Частичная функция f называется частично рекурсивной,
если существует такая конечная последовательность частичных функций
g0, …, gk что gk=f и каждая gi, i≤k либо базисная, либо получается из
некоторых предыдущих регулярной суперпозицией, примитивной рекурсией
или минимизацией. Эта последовательность g0, …,gk называется определяющей последовательностью для f. Если для всюду определенной
частично рекурсивной функции f существует определяющая
последовательность, состоящая только из всюду определенных функций, то f называется рекурсивной.
В следующем параграфе будет доказано, что любая всюду определенная
частично рекурсивная функция является рекурсивной.
Из данного определения и приведенных выше замечаний о сохранении
вычислимости операторами S, R, М легко следует, что всякая частично
рекурсивная функция является вычислимой.
Обратное утверждение носит название тезиса Чёрча: любая вычислимая частичная частично рекурсивна.
Исторически именно это утверждение было первым точным математическим
определением понятия (алгоритмически) вычислимой функции.
Имеет место следующая теорема, доказательство которой мы опустим из-
за его громоздкости.
Теорема 2
Класс частично рекурсивных' функций совпадает с классом функций,
вычислимых, по Тьюрингу.
Таким образом, тезис Тьюринга эквивалентен .тезису Чёрча.
Пусть k, nw а — некоторое отображение множества {1,...,k} в множество {1,...,n} f— k-местная частичная функция. Будем говорить, что n-местная частичная функция g получена из f подстановкой ее, если для любых m1,.., mnw имеет место соотношение:
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, nw;
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(I11S(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), af— функция
полученная из функции -- подстановкой а. Тогда для функции δ
справедливо равенство δ=S(sg), S(+,--,f)). Из рекурсивности функций sg — и предложения получаем, что функция идентификации δ является рекурсивной.
Для задания, рекурсивных функций и изучения их свойств удобно-
пользоваться специальным формальным языком R.
Пусть V={Ui I i} — множество переменных, элементы лоторого
будем обозначать буквами х, у, z, w, и, возможно с индексами.
Пусть (R,F,M) — некоторая конечная сигнатура такая, что
F F0={0,s,+,•) где 0 символ нульместной функции, s — символ одноместной функции, +, • — символы двухместных функций; RR0 ={<}, где < символ двухместного предиката.
Определение выражений, (синтаксис) языка R будет зависеть еще и от семантики этого языка. Поэтому определение синтаксиса и семантики будет вестись, одновременно, но прежде всего зададимся фиксированной алгебраической системой сигнатуры с основным множеством w и такой, что значения символов сигнатуры 0 = (R0,F0,Mn) совпадают с функциями и предикатом, обозначенными этими символами ранее (например, символу • соответствует операция умножения натуральных чисел).
Итак, будем одновременной индукцией определять понятие -терма, -формулы (более точно было бы говорить об термах и -формулах), множества свободных переменных FV(t) и FV() -терма t и -формулы соответственно, натуральное число t[] и истинностное значение []{и,л} для всякой интерпретации где ХV,FV(t) FV()X;
а) символ 0 является -термом, FV(0=) и 0[=0];
б)переменная хУ является -термом, FV(x)={x}, x[]=(x);
в)если fF — n-местный функциональный символ, t1,…,tn -термы; то
-терм f(f1,...,tn); FV(f(t1,…,tn))=FV(t1)U…UFV(tn); F(t1,…,tn) []=f (t1[],…,tn[])
здесь f-n местная операция Алгебраической системы соответствующая сигнатурному символу f;
г) если (Q— n-местный предикатный символ из Rat1,…,tn-термы, то Q(t1,…,tn) -формула, FV(Q(t1,…,tn))=FV(t1)U…UFV(tn); Q(t1,…,tn) [] здесь Q— n-местный предикат, соответствующий в алгебраической системе предикатному символу Q; д)Если t1,…,t2-термы, t1≈t2 -формула, FV(t1≈t2) =FV(t1)UFV(t2), (t1≈t2) [] = и <=> t1[]=t2[];
е)Если и ψ -формула то ┐,(,,ψ) для {∧,∨,} -формулы, fV(┐) = FV(), FV(,,ψ)=FV() U FV(ψ) и (┐)[] = ┐([]) где ┐ ∧,∨, операции определены на множестве {и,л} таблицей (1) c заменой «о» на «л» и «1» на «и»
ж)Пусть -формула, xV и для любой интерпретации 1:X для которой xX и FV()XU{x}cсуществует такое же n, что [] = и для =1 U{<x,n>}; тогда x-терм, FV(x) = FV() \ {x} и (x)[] -наименьшее n0 для которого [’]= и где ’=( \ {<x,x>})U{<x,n0>} Индукцией по построению -терма (-формулы) легко устанавливается, что для любых интерпретаций 0:x0, 1:x1 с таких, что FV()x0 ∩ x1 и для всех xFV()0 (x)= 1 (x) и для всех выполняется равенство [0]= [1].
Как обычно, в место +(t1,t2)•(t1,t2)) будем писать (t1+t2)((t1•t2)) и (t1<t2). Вместо <( t1,t2 ). Кроме того, будем пользоваться обычными
сокращениями для термов и формул, принятыми в арифметике и
исчислении высказываний (например, вместо (x+((z•z)+(x•y))) и ((∧ψ) будем писать соответственно x+z2 +xy и (∧ψ) ).
Для -формулы и интерпретации ; x FV()x, часто вместо «[] = и» будем писать «[] истинно» или просто «[]». А вместо «[] = ∧» будем писать «[] ложно» или «┐[]».
Пусть — -терм или (-формула). Вхождение переменной x в называется свободным, если оно не находится в пол слове вида xявляющемся -термом. Если вхождение переменной в не является свободным, то оно называется связанным. Легко проверить, что множество FV() состоит в точности из переменных, имеющих свободные вхождениям в .
Пусть в-терм (-формула), x1,…,xnV - различные переменные, t1,…tn-терм такие, что для любого i{1,…,n} и любого yV(t1) ни одно свободное вхождение в переменной Xi не содержится в терме вида являющемся y под словом .
будет обозначать результат замены всех свободных вхождений переменных х1,..,хn на -термы - t1,...,tnсоответственно.
Ю. Л. Ершов, Е. Л. Палютиа
Индукцией по построению -терма и -формулы без труда устанавливается следующее.
Предложение 3.
Если -терм (-формула) х1,..,хnV — различные переменные, t1,...,tn — -термы такие, что для , х1,..,хn, t1,...,tn выполнены сформулированные выше условия, то
1) 1= является -тepм (-формулой), в такой для любой интерпретации :x. В такой, что (FV()\{х1,..,хn})U…UFV(tn)xвыполняется равенство 1[]=[] где ’ = {<y,(y)>|yFV ()}. Про - терм (-формулу) будем говорить, что получен из подстановкой - термов t1,...,tnвместо переменных х1,..,хn.
К сожалению, условия для возможности подстановки -термов вместо переменных не всегда выполнены. Чтобы всегда иметь возможность для подстановки, введем следующие понятия. Будем говорить, что -терм (-формула) получается из -терма (-формулы) , заменой связанной переменной, если получается из заменой вхождения -терма xна y()xyгде yFV(). -термы (-формулы) и 1 называются конгруэнтными, если существует такая последовательность 0,…,n что o = 1 ; o = ’; I+1 ,I<n, получается из заменой связанной переменной. Очевидно, что отношение конгруэнтности является эквивалентностью на множестве -термов и -формул.
Предложение 4.
Если и ' — конгруэнтные -тёрмы или -формулы, то FV(=FV(’))для любой интерпретации :FV() имеем []=’[].
Доказательство 3.
Индукцией по длине легко показать, что если 1 получается из заменой связан ной переменной, то утверждение предложения истинно. Далее индукция по длине последовательности 0,…,n из предыдущего определения.
Отметим, что для любого -терма ( -формулы) , любого набора попарно различных переменных x1,…,хn любых -термов t1,...,tn существует -терм (-формула) ' такой (такая), что ' конгруэнтен (конгруэнтна) и для ' выполнены условия для подстановки пользуясь этим свойством и предложением 4, будем впредь использовать запись , не заботясь о выполнении условий на связанные переменные считая, что если эти условия не выполнены, то есть для -терма (-формулы) ', конгруэнтного (конгруэнтной) в, причём для ' все условия для подстановки уже выполнены.
Напомним, что подмножество XAn называется n-местным предикатом на А. В дальнейшем под предикатами будем понимать предикаты на . Если n-местный предикат, то n-местная функция nx определенная следующим образом: для любых m1,…,mn случаев,
называется представляющей функцией для X. Наряду с представляющей функцией x предиката X часто используют характеристическую функцию Xх предиката X, которая связана с функцией x соотношением Xx= sg(x) предикат X называется рекурсивным, если его пред уставляющая функция x рекурсивна.
Алгебраическая система называется рекурсивной, если все функции и предикаты, соответствующие символам сигнатуры , являются рекурсивными.
В дальнейшем, говоря о -формулах и -термах (определение которых зависит от фиксированной алгебраической системы , будем всегда предполагать, что — рекурсивная алгебраическая система. Заметим, что предикаты ≈,< являются рекурсивными, так как
представляющей функцией для ≈ является функция идентификации δ а представляющей функцией для < будет рекурсивная функция sg(S(I21) – I22). С каждым -термом ( -формулой) можно связать
семейство функций (предикатов), которые реализуются этим -термом ( -формулой). Для обозначения этих
функций (предикатов) будем использовать расширение языка, R добавив новую пару [,] символов квадратных, скобок.
Перейдем к точным, определениям.
Если t- -терм для ij то через t[x1,…,хn] будем обозначать n-местную функцию, принимающую на n-ке <m1,…,mn> значение t[], где ={<x1,m1>│I=1,…,n}. Если - -формулой и FV(){x1,…,хn}, x1xj, для ij, то через будем обозначать предикат {<m1,…,mn>│[]={<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: Xw, где Хwn для некоторого nх.
Спасибо за то что прочитали эту курсовую, надеюсь вы почерпнули из прочитанного материала много нового и познавательного.
Список Литературы
-
Марченко С.С. Элементарные рекурсивные функции. М.: МЦНМО, 2003.
-
Кузнецов А.В. К теореме о канонической форме для ординально-рекурсивных функций. В книге Гудстейн Р. Л. Математическая логика. М.: ИЛ, 1961, с. 149-154.
-
Смальян Р. Теория формальных систем. М.: Наука, 1981.
-
Косовский Н. К. Элементы математической логики и ее приложения к теории субрекурсивных алгоритмов. Л., Из-во Ленинград. ун-та, 1981.
-
Гжегорчик А. Некоторые классы рекурсивных функций. В книге: Проблемы математической логики. М., Мир, 1970, с. 9-49.