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

 

Содержание

Введение ------------------------------------------------------------------------2

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

Определение -----------------------------------------------------------------------------4

Теорема 2. --------------------------------------------------------------------5

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

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

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

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

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

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

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

Заключение  -------------------------------------------------------------------------------------------11

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

Введение

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

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

Ниже приведём множество примеров и доказательств этой теоремы таких как:

g=S^n,k-1(f, I ⁿa1,…,I ⁿak)

и предложения как на пример:

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

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

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

4)двухместная функция усеченной разности •,

                                                             ___

5)одноместные функции sg и sg,

6)двухместная  функция  идентификации  6.

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

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

 

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

отображение

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

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

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

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

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

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

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

местная функция f: w°® w будет состоять из одной пары <Æ, п> для

некоторого nÎw и часто будет отождествляться с числом n. Всюду в даль-

нейшем буквы т, k, n, I и j ], возможно с индексами, будут обозначать

натуральные числа.

Пусть f: X ® w — n-местная частичная функция. Если <m₁,.., m_л>ÎX, то f(m₁,.., m_л) — это значение функции f на п – ке <m₁,.., m_л>.  Если  <m₁,.., m_л>ÏX, то будем говорить, что f(m₁,.., m_n ) не определено или что f не определена на n-ке < m₁,.., m_n >    . Ясно, что для задания частичной n-местной функции достаточно для любой n-ки  <m₁,.., m_n>  сказать, определено ли f(m₁,.., m_n) и если определено, то указать число   k = f (m₁,.., m_n).   Если f  и g — частичные функции, то будем писать f(m₁,.., m_n)=g(m₁,.., m_n)

когда    обе    части    равенства    определены    и    равны,    либо обе части

равенства не определены.

Пусть  семейство всех n - местных частичных функций,  а = U n, семейство всех частичных функции.

Определим на семействе  всех частичных функций операторы S, R, М, которые сохраняют вычислимость функций.

Пусть n, kÎw, f—(n+1)-местная частичная функция, go,..., g_n — k-

местные частичные функции. Определим k-местную частичную функцию h

следующим образом: h(m₁,.., m_k) не определено, если хотя бы одна из

частичных функций go,..., g_n не определена на _< m₁,..,m_k > и если

все  go,...,g_n определены  на < m₁,.., m_k>, то h(m₁,.., m_k)=f(go(m₁,.., m_k)…, g_n(m₁,.., m_k)).

Будем говорить, что h получена регулярной суперпозицией из f, g₀, …, g_n и обозначать это следующим образом h=S^k,n(f, g₀, …, g_n). Оператор (регулярной суперпозиции)- S^k,n является всюду определенным отображением из n+1 X ⁿ⁺¹ k в k и сохраняет вычислимость, т.е. если частичные функции f Î  n+1; g₀, …, g_n Î k вычислимы, то и частичная функция S^k,n (f, g₀, …, g_n) вычислима. Верхние индексы, у оператора S будут опускаться и вместо S(f, g₀, …, g_n) будет, как правило, использоваться более привычное, но менее точное обозначение f(g₀,..., g_n). Пусть       n Î w,fÎn,gÎn+2.Определим по f и g (n + 1) - местную частичную функцию h так, что для любых m₁,.., m_n Î w

h(m₁,.., m_n,0)=f(m₁,.., m_n);

 

 h(m₁,.., m_n ,k+1) не    определено, если h(m₁,.., m_n, k) не определено и h(m₁,.., m_n, k+1) = g(m₁,..,m_n,k), h(m₁,.., m_n,k)), если h(m₁,.., m_n, k) определено. Очевидно, что h однозначно определена по f и g и вычислима, если вычислимы  / и указанное определение h по / и g задает оператор h=R ⁿ⁺¹:n X n+2 ® n+1  который назовем оператором  примитивной рекурсии. Про h=функцию h = R ⁿ⁺¹(f, g) будем говорить, что она получила примитивной рекурсией из функций f и g. Верхний индекс у оператора Rⁿ⁺¹ будем опускать.

Пусть nÎw,fÎn+1. Определим по f такую n-местную частичную

функцию g, что для любых k, m₁,.., m_n Î w тогда и только тогда, когда f(m₁,.., m_n,0)=0 и k=0 или k>0 и f(m₁,.., m_n,0) определены и не равны нулю, а f(m₁,.., m_n,k)=0. Ясно, что такая функция д существует и однозначно определена по f; кроме того, если f — вычислимая функция, то из определения g видно, как вычислять g. Таким образом, задан оператор M ⁿ — оператор минимизации — из n+1 в n если g= M ⁿ (f) то будем говорить, что g получена минимизацией из f .

Базисными функциями называются функции о, s, I ⁿm  (1≤m≤n) где о —

одноместная функция, которая па любом n принимает значение 0, s — одноместная функция, принимающая на числе n значение n+1, a I ⁿm  — n-местная функция, принимающая на наборе (k1,…,kn) значение km. Очевидно, что базисные функции вычислимы.

Определение.

Частичная функция f называется частично рекурсивной,

если существует такая конечная последовательность частичных функций

g₀, …, g_k что g_k=f  и каждая g i, i≤k либо базисная, либо получается из

некоторых предыдущих регулярной суперпозицией, примитивной рекурсией

или      минимизацией.      Эта      последовательность g₀, …,g_k называется определяющей последовательностью для f. Если для всюду определенной

частично       рекурсивной      функции      f      существует      определяющая

последовательность, состоящая только из всюду определенных функций, то f называется рекурсивной.

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

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

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

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

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

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

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

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

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

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

Теорема 2

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

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

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

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

g(m₁,.., m_n))=(m_a1,..,m_ak).

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

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

 

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

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

 

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

                                            g=S^n,k-1(f, I ⁿa1,…,I ⁿak)

 

Предложение 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(I¹1 S(I³3)). Из равенств   n•0=0 и n•(m+1) =

n•m+n следует,    что    функция равна R(0,I¹1 +I³3)

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

 

Она равна   R(0, I²1)  поэтому рекурсивна. Так как n — (m+1)=(n — m) — 1, то функция -- равна R (I¹1, I³3 – 1) следовательно, также является рекурсивной.

Рекурсивность функций следует из равенств sg = R(o,s (0(I²1))) и sg=R(1,0(I²1)). Пусть 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]=f^Wå   (t1[h],…,tn[h])

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

г) если (Q— n-местный предикатный символ из Ra t1,…,tn _å-термы, то Q(t1,…,tn) _å-формула, FV(Q(t1,…,tn))=FV(t1)U…UFV(tn); Q(t1,…,tn) [h] здесь Q^Wå— 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+z² +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 и Q¹ называются конгруэнтными, если существует такая последовательность Q0,…,Qn  что Q_o = Q1 ; Q_o = Q’; Q_I+1 ,I<n,    получается из Q заменой связанной переменной. Очевидно, что отношение конгруэнтности является эквивалентностью на множестве _å-термов и _å-формул.

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

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

 

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

 

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

Отметим, что для любого _å-терма ( _å-формулы) Q, любого набора попарно различных переменных x₁,…,х_n любых _å-термов  t₁,...,t_n существует _å-терм (_å-формула) 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(I²1) – I²2). С       каждым       _å-термом        (    _å -формулой)       можно       связать

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

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

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

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

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

t[x₁,…,х_n] =  [ y₁,…,y_n].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

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

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

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

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

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

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

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

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

Содержание Введение ------------------------------------------------------------------------2 Рекурсивные функции --------------------------------------

Больше работ по теме: