Редактирование: Примитивно рекурсивные функции
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 40: | Строка 40: | ||
===Примитивно рекурсивные функции=== | ===Примитивно рекурсивные функции=== | ||
+ | |||
+ | ==== Основные определения ==== | ||
+ | Рассмотрим следующие правила преобразования функций: | ||
+ | |||
+ | ===== Подстановка ===== | ||
+ | Рассмотрим <tex> k </tex>-местную функцию <tex> \mathrm{f}(x_1,\ldots,x_k) </tex> и <tex> k </tex> <tex>n </tex>-местных функций <tex> \mathrm{g_i}(x_1,x_2,\ldots,x_n) </tex>. Тогда после преобразования у нас появится <tex> n </tex>-местная функция <tex>\mathrm{F} </tex>, такая что: | ||
+ | <tex> \mathrm{F} = \mathrm{f}(\mathrm{g_1}(x_1,\ldots,x_n),\ldots, \mathrm{g_k}(x_1,\ldots,x_n)) </tex>. | ||
+ | |||
+ | ===== Рекурсия ===== | ||
+ | Рассмотрим <tex> k </tex>-местную функцию <tex> \mathrm{f} </tex> и <tex> (k + 2) </tex>-местную функцию <tex> \mathrm{h} </tex>. Тогда после преобразования у нас будет <tex> (k+1) </tex>-местная функция <tex> \mathrm{g} </tex>, которая определена следующим образом: | ||
+ | |||
+ | <tex>\mathrm{g}(x_1,\ldots,x_n,0)=\mathrm{f}(x_1,\ldots,x_n)</tex> | ||
+ | |||
+ | <tex>\mathrm{g}(x_1,\ldots,x_n,y+1)=\mathrm{h}(x_1,\ldots,x_n,y,\mathrm{g}(x_1,\ldots, x_n,y))</tex> | ||
+ | |||
+ | При этом будем говорить, что рекурсия запускается по аргументу <tex> y </tex>. | ||
{{Определение | {{Определение |