Викия

Математика

Частично рекурсивная функция

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Частично рекурсивная функция - частичная функция f, полученная из простейших функций 0, s, ~I_m^n конечным числом операций подстановки, примитивной рекурсии и минимизации.

Простейшие (базисные) функции:Править

  • Нуль-функция

~0(x)=0

  • Функция следования

~s(x)=x+1

  • Функция выбора аргумента

~I_m^n (x_{1},x_{2},\cdots,x_{n})=x_m

Операции над базисными функциямиПравить

  • Подстановка (суперпозиция).

~f_1(x_1,...,x_n), ...f_2(x_1,...,x_n)

~g(f_1(x_1,...,x_n), ...f_2(x_1,...,x_n))

Операцией подстановки называется операция вида ~S(g,f_1,...,f_n)

  • Примитивная рекурсия.

Операцией примитивной рекурсии называется операция вида R(g,h), где для всех натуральных значений ~x_1,x_2,...x_n выполняется:

~f(x_1,x_2,...x_n,0) = g(x_1,x_2,...x_n)

~f(x_1,x_2,...x_n,y+1) = h(x_1,x_2,...x_n,y,g(x_1,x_2,...x_n))

  • Минимизация.

Операцией минимизации называется операция вида ~M_y(f(x_1,x_2,...x_n,y)=x_{n+1}), где вычисляется значение ~f_1(x_1,...,x_n,0), потом ~f_1(x_1,...,x_n,1) и так далее до тех пор, пока на шаге k не получим ~x_{n+1}, число k и будет результатом действия операции.

Викия-сеть

Случайная вики