logo
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Оператор минимизации (- орератор).

Def. Оператором минимизации (наименьшего числа оператора) называется преобразование (n+1)-местной функции (в общем случае частичной)  в n-местнуб f, такую, что для любых х1, х2, …хn, у равенство f(х1, х2, …хn)=у имеет место лишь в том случае, если определены и не равны нулю значения ( х1, …, хn, 0), …, ( х1, …, хn, у-1) и при этом ( х1, х2, …хn, у)=0. Применение оператора минимизации обозначают [, (y)], где у - исчезающий аргумент.

Говорят, что n-местная арифметическая функция f: NnN получается из функции : Nn+1N с помощью -оператора, если выполнено условие: для любых k1, k2,…, kn, kN.

f(k1, k2,…, kn)=k,

тогда и только тогда, когда для всех l<k значения ( k1, k2,…, kn, l) определены и отличны от нуля, а значение ( k1, k2,…, kn, k) определено и равно нулю.

Если f получается из функции  с помощью оператора наименьшего числа , то пишут:

f(x1, x2,…, xn)=y[(x1,…, xn, y)=0].

Важным свойством -оператора является то, что с его помощью из вычислимой функции всегда получается частичная вычислимая функция f. Именно, если имеется алгоритм для вычисления , то значение f(x1, x2,…, xn) может вычисляться следующим образом:

Пример:

f(x)=y[12*y-x=0]. Тогда f(x)=x/2 при всех четных значениях хN.

Замечание:

Примитивно-рекурсивные функции всегда определены (имеют значения) для любых значений аргументов. Иначе обстоит дело с функциями, полученными при помощи -оператора. Для некоторых комбинаций значений аргументов они могут быть не определены, потому что исходная функция не принимает нулевых значений.

Пример:

det f(x)=[J21(x, y), (y)].

Полученная функция f(х) обладает следующими свойствами:

f(0)=0, f(k) не существует при k0. Последнее означает, что для заданной функции J21(x, y) -оператор не может построить f(k) kN, так как при x=k функция (x, y)= J21(x, y) ни для какого значения у не будет равной нулю.

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4