НАИМЕНЬШЕГО ЧИСЛА ОПЕРАТОР

m-оператор, оператор минимизаци и,- способ построения новых функций из других функций, состоящий в следующем. Пусть gесть (n+1)-местная арифметич. функция, т. е. функция, аргументы к-рой так же, как и она сама, принимают значения в множестве натуральных чисел. Функция gпредполагается частичной функцией, т. е. определенной не обязательно для всех значений аргументов. Говорят, что n-местная арифметич. функция f получается из функции gс помощью Н. ч. о., если выполнено условие: для любых натуральных чисел

тогда и только тогда, когда для всех значения определены и отличны от нуля, а значение определено и равно нулю. Если f получается из функции gс помощью Н. ч. о., то пишут:

Важным свойством Н. ч. о. является то, что с его помощью из вычислимой функции g всегда получается частичная вычислимая функция f. Именно, если имеется алгоритм для вычисления g, то значение может вычисляться следующим образом. Вычисляем Если процесс вычисления закончится, т. е. значение определено, и то полагаем а если то начинаем вычислять . Если процесс закончится и то полагаем а если то переходим к вычислению и т. д. Процесс вычисления закончится, если найдется такое у, что для всех значение определено и отлично от нуля, а определено и равно нулю.

Тогда

Н. ч. о. играет важную роль в определении класса частично рекурсивных функций.

В. Е. Плиско.