Оператор минимизации (- орератор).
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: NnN получается из функции : Nn+1N с помощью -оператора, если выполнено условие: для любых k1, k2,…, kn, kN.
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) может вычисляться следующим образом:
вычисляется (x1, x2,…, xn, 0);
если процесс вычисления закончился, то есть значение (x1, x2,…, xn, 0) определено, и (x1, x2,…, xn, 0)=0, то полагаем f(x1, x2,…, xn)=0, а если (x1, x2,…, xn, 0)0, то начинают вычислять (x1, x2,…, xn, 1). Если процесс вычисления закончился и (x1, x2,…, xn, 1)=0, то полагают f(x1, x2,…, xn)=1, а если (x1, x2,…, xn, 1)0, то переходят к вычислению (x1, x2,…, xn, 2) и так далее.
Процесс вычисления закончится, если найдется такое у, что для всех z<y значение (x1, x2,…, xn, z) определено и отлично от нуля, а (x1, x2,…, xn, у) определено и равно нулю. Тогда 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) не существует при k0. Последнее означает, что для заданной функции J21(x, y) -оператор не может построить f(k) kN, так как при x=k функция (x, y)= J21(x, y) ни для какого значения у не будет равной нулю.
Yandex.RTB R-A-252273-3
- Математическая логика
- Парадигмы формальной логики.
- Предмет, цель, задачи и содержание читаемого курса лекций.
- Место читаемого курса о законах и формах правильного мышления.
- Концептуальный базис математической логики.
- Построение математической логики.
- Классическая логика высказываний.
- Язык классической логики предикатов (я.Л.П.).
- Примеры:
- Алгебра логики предикатов.
- Пояснения:
- Квантификация предикатов.
- Эквивалентные преобразования кванторных формул.
- Классические логические исчисления.
- Цель классических и.В. И и.П.
- Метасимволика и.В. И и.П.
- Построение логических исчислений.
- Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.
- Основные требования к алгоритмам.
- Основная терминология теории алгоритмов.
- Основные теоремы теории алгоритмов.
- Параметры алгоритма.
- Основная гипотеза теории алгоритмов.
- Алгоритмические (формальные математические) модели.
- Блок-схемы алгоритмов.
- Машина Тьюринга. Машина Тьюринга т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.
- 1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
- Формальное определение машины Тьюринга.
- Основной тезис Тьюринга.
- Нормальные алгорифмы (алгоритмы).
- Рекурсивные функции.
- Примитивно-рекурсивные функции.
- Оператор минимизации (- орератор).
- Основной тезис Черча.
- Алгоритмически неразрешимые проблемы.