Одним из свойств алгоритма является его массовость. Это означает, что алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы отображения не одного, а целого множества входных слов в соответствующие им выходные слова.
Таким образом, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач.
Оказывается, что существуют такие классы задач, для решения которых, нет и не может быть единого универсального приема. Проблемы решения такого рода задач называют алгоритмически неразрешимыми проблемами. Однако алгоритмическая неразрешимость задачи того или иного класса вовсе не означает невозможность решения любой конкретной задачи из этого класса. Речь идет о невозможности решения всех задач данного класса одним и тем же приемом.
Таким образом, задачи ( проблемы ) можно разделить на алгоритмически разрешимые алгоритмически неразрешимые.
Примером алгоритмически разрешимой проблемы является проблема доказательства тождеств в обычной алгебре. Существует единый конструктивный прием: раскрытие скобок, приведение подобных членов, и. т. п., позволяющий за конечное число шагов решить, является ли любое заданное соотношение тождеством.
Переход от интуитивного понятия алгоритма к точному понятию рекурсивной функции, Машины Тьюринга или нормального алгоритма позволил доказать алгоритмическую неразрешимость ряда проблем.
Одним из первых результатов такого типа является доказательство неразрешимости проблемы распознавания выводимости в математической логике, выполненное Чёрчем в 1936 году. Результат этого доказательства формулируется как теорема Чёрча. Это доказательство довольно громоздко, поэтому здесь приведено не будет. Суть же его сводится к доказательству нерекурсивности функции, решающей эту задачу.
В качестве примера доказательства алгоритмической неразрешимости рассмотрим проблему распознавания самоприменимости.
Существуют самоприменимые и несамоприменимые алгоритмы. Примером самоприменимого алгоритма является так называемый тождественный алгоритм в любом алфавите А,содержащем две или более буквы.
Этот алгоритм применим к любому слову Р в алфавите А и перерабатывает любое входное слово в себя. Примером несамоприменимости алгоритма является так называемый нулевой алгоритм в любом конечном алфавите В.
Это алгоритм задается схемой, содержащей единственную подстановку
àу , где у- любая буква алфавита В.
По своему определению он не применим ни к одному входному слову, а значит и к своему изображению.
Проблема распознавания самоприменимости алгоритмов состоит в том, чтобы найти единый конструктивный прием, позволяющий за конечное число шагов по схеме любого заданного алгоритма узнать, является ли этот алгоритм самоприменимым или несамоприменимым.
Доказательство алгоритмической неразрешимости этой проблемы будем проводить, используя алгоритмическую систему Тьюринга.
Пусть в машине Тьюринга МТ зафиксирована какая-нибудь конфигурация.
Возможны два случая:
машина применима к этой конфигурации, то есть после конечного числа тактов она завершает работу в заключительной конфигурации;
машина не применима к этой конфигурации, то есть никогда не переходит в заключительную конфигурацию, а попадает в бесконечный процесс переходов.
Предположим, что на информационной ленте (ИЛ) МТ изображен ее собственный шифр (то есть шифр таблицы соответствия и исходной конфигурации), записанной в алфавите машины.
Если МТ применима к такой конфигурации, то будем называть ее самоприменимой, в противном случае - несамоприменимой.
Проблема распознавания самоприменимости состоит здесь в следующем: по любому заданному шифру требуется установить, к какому классу относится машина, зашифрованная им - к классу самоприменимых или несамоприменимых?
Доказательство:
Предположим, что такая машина М существует. Тогда в М всякий самоприменимый шифр перерабатывается в некоторый символ С, несамоприменимый – в символ Н.
В таком случае можно было бы построить и такую машину М1, которая по-прежнему перерабатывает несамоприменимые шифры в Н, в то время, как к самоприменимым шифрам М1 уже не применима. Этого можно добиться путем изменения схемы машины М( таблицы соответствия ), чтобы после появления символа С вместо остановки машина стала бы неограниченно вырабатывать этот символ.
Итак, М1 применима ко всякому несамоприменимому шифру
( вырабатывает при этом символ Н) и не применима к самоприменимым шифрам. Однако, это приводит к противоречию.
Действительно:
Пусть М1 самоприменима, тогда она применима к своему шифру М1’ и перерабатывает его символ Н, но появление этого символа должно означать, что машина несамоприменима;
Пусть М1 несамоприменима, тогда она применима к М1’, что должно означать, что М1- самоприменима.
Полученные противоречия доказывают неразрешимость этой проблемы.
0 коммент.:
Отправить комментарий