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

Содержание

Введение ------------------------------------------------------------------------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=Sn,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

некоторого 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)

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

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

Пусть

Теорема 2/h1>

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

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

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

Пусть 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=fa

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

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

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

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

g=Sn,k-1(f, I ⁿa1,Е,I ⁿak)

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

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

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

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

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

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

образом:

Заключение

В этой курсовой было определено понятие рекурсивного предиката, как предиката, представляющая функция которого является рекурсивной. Таким образом, рекурсивные предикаты это в точности такие предикаты 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.