ФЭНДОМ


Частично рекурсивная функция - частичная функция 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 и будет результатом действия операции.

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


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

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

Также на ФЭНДОМЕ

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