Рекурсивные функции
Реферат - Математика и статистика
Другие рефераты по предмету Математика и статистика
?? является функция идентификации ? а представляющей функцией для < будет рекурсивная функция sg(S(I21) I22). С каждым-термом ( -формулой) можно связать
семейство функций (предикатов), которые реализуются
этим-термом ( -формулой). Для обозначения этих
функций (предикатов) будемиспользовать расширение языка, R добавив новую пару [,] символовквадратных, скобок.
Перейдем к точным, определениям.
Если t- -терм для ij то через t[x1,…,хn] будем обозначать n-местную функцию, принимающую на n-ке ¦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-ке чисел .
Так же рассмотрели частично рекурсивные функции совпадающие с классом функций, вычислимых, по Тьюрингу.
В этом реферате мы привели способ уточнения понятия вычислимой функции который можно назвать алгебраическим, так как определяемый класс функций будет порождаться из некоторых простейших функций с помощью некоторых операций. Под частичной функцией мы понимаем f: X w, где Х wn для некоторого nх.
Спасибо за то что прочитали эту курсовую, надеюсь вы почерпнули из прочитанного материала много нового и познавательного.
Список Литературы
- Марченко С.С. Элементарные рекурсивные функции. М.: МЦНМО, 2003.
- Кузнецов А.В. К теореме о канонической форме для ординально-рекурсивных функций. В книге Гудстейн Р. Л. Математическая логика. М.: ИЛ, 1961, с. 149-154.
- Смальян Р. Теория формальных систем. М.: Наука, 1981.
- Косовский Н. К. Элементы математической логики и ее приложения к теории субрекурсивных алгоритмов. Л., Из-во Ленинград. ун-та, 1981.
- Гжегорчик А. Некоторые классы рекурсивных функций. В книге: Проблемы математической логики. М., Мир, 1970, с. 9-49.