МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. Математическая логика
 Скачать 1.08 Mb.
|
|
Оператор минимизации (- орератор). 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 Если 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) не существует при k0. Последнее означает, что для заданной функции J21(x, y) -оператор не может построить f(k) kN, так как при x=k функция (x, y)= J21(x, y) ни для какого значения у не будет равной нулю. Основной тезис Черча. Утверждение: «Какова бы ни была вычислимая неотрицательная функция от неотрицательных целочисленных аргументов, существует тождественно равная ей рекурсивная функция» - основной тезис Черча. Перенеся тезис Черча на алгоритмы, сопутствующие рекурсивным функциям, можно высказать и следующую гипотезу: «Каков бы ни был алгоритм, перерабатывающий наборы целых неотрицательных чисел в целые неотрицательные числа, существует алгоритм, сопутствующий рекурсивной функции, который ему эквивалентен». Приведенные гипотезы означают, что выполнение алгоритма в определенном смысле эквивалентно вычислению значений рекурсивной функции, а невозможность рекурсивной функции означает и невозможность алгоритма (так как для каждого алгоритма должна быть рекурсивная функция, а ее-то в данном случае и нет). Напомним, что тезис Черча и следующие из него другие гипотезы не имеют доказательства и принципиально не могут быть доказаны, так как в них речь идет об алгоритмах в интуитивном смысле, не являющихся математическими объектами. Алгоритмически неразрешимые проблемы. Массовые проблемы, для которых не существует эффективных методов разрешения, называются алгоритмически неразрешимыми проблемами. В интуитивном смысле массовая (алгоритмическая) проблема – это бесконечный класс родственных единичных конкретных проблем, правильный ответ для каждой из которых получается применением алгоритма. Фактически произвольную массовую проблему можно сформулировать как проблему распознавания некоторого свойства Р элементов бесконечного множества М; при этом единичные проблемы. составляющие массовую проблему, связываются с элементами множества М, и каждая из них состоит в том, что требует узнать, обладает или нет свойством Р соответствующий элемент множества М. Поэтому задача ставится так: найти алгоритм, применимый к любому элементу множества М и для каждого данного хМ дает «1» или «0» в зависимости от того, обладает или нет элемент х свойством Р. Массовая проблема называется неразрешимой, если такого алгоритма нет. Очевидно, принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения проблем, из которых вытекало бы (если бы они были разрешимы) существование объектов. Понятие алгоритмической неразрешимости уточняется с привлечением математических понятий машины Тьюринга, рекурсивных функций, нормальных алгоритмов и других. Известны два способа доказательства неразрешимости: прямой и косвенный, использующий сводимость к данной проблеме другой массовой проблеме, неразрешимость которой была доказана раньше. Напоминание: В настоящее время алгоритмические проблемы формируются как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождения такого алгоритма в случае, если он существует. |