Одним из свойств алгоритма является его массовость. Это означает, что алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы отображения не одного, а целого множества входных слов в соответствующие им выходные слова. Таким образом, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач.
Оказывается, что существуют такие классы задач, для решения которых нет и не может быть единого универсального приема. Проблемы решения такого рода задач называют алгоритмически неразрешимыми проблемами. Однако алгоритмическая неразрешимость проблемы решения задач того или иного класса вовсе не означает невозможность решения любой конкретной задачи из этого класса. Речь идет о невозможности решения всех задач данного класса одним и тем же приемом.
Таким образом, задачи (проблемы) можно разделить на алгоритмически разрешимые и алгоритмически неразрешимые. Примером алгоритмически разрешимой проблемы является проблема доказательства тождеств в обычной алгебре. Существует единый конструктивный прием (раскрытие скобок, приведение подобных членов), позволяющий за конечное число шагов решить, является ли любое заданное соотношение тождественным.
Переход от интуитивного понятия алгоритма к точному понятию рекурсивной функции (машины Тьюринга, нормального алгоритма) позволил доказать алгоритмическую неразрешимость ряда проблем.
Одним из первых результатов такого типа является доказательство неразрешимости проблемы распознавания выводимости в математической логике, выполненной Черчем в 1936 г. Результат этого доказательства формулируется как теорема Черча (5). Проблема распознавания выводимости алгоритмически неразрешима.
Тем самым не только выясняется причина безуспешности всех прошлых попыток создания соответствующего алгоритма, но и обнаруживается полная бессмысленность таких попыток. . Доказательство данной теоремы Черча рассматривать не будем ввиду его сложности. Отметим лишь, что суть его сводится к доказательству нерекурсивности функции, решающей данную задачу.
В качестве примера доказательства алгоритмической неразрешимости рассмотрим проблему распознавания самоприменимости. Существуют как самоприменимые, так и несамоприменимые алгоритмы. Примером самоприменимого алгоритма является так называемый тождественный алгоритм в любом алфавите А, содержащем две или более двух букв. Этот алгоритм применим к любому слову р в алфавите А и перерабатывает любое входное слово в себя.
Примером несамоприменимого алгоритма является так называемый нулевой алгоритм в любом конечном алфавите В. Этот алгоритм задается схемой, содержащей единственную подстановку ® у (где у—любая буква алфавита В). По своему определению он не применим ни к какому входному слову, а значит, и к своему изображению.
Проблема распознавания самоприменимости алгоритмов состоит в том, чтобы найти единый конструктивный прием, позволяющий за конечное число шагов по схеме любого данного алгоритма узнать, является алгоритм самоприменимым или несамоприменимым.
Доказательство алгоритмической неразрешимости данной проблемы будем проводить, используя алгоритмические системы Тьюринга.Для этого сформулируем проблему самоприменимости в терминах машины Тьюринга. Пусть в машине Тьюринга зафиксирована какая-нибудь конфигурация. Возможны два случая:
1) машина применима к этой конфигурации, т. е. после конечного числа тактов она останавливается в заключительной конфигурации;
2) машина не применима к этой конфигурации. Это означает, что машина никогда не переходит в заключительную конфигурацию, она впадает в бесконечный процесс.
Предположим теперь, что на ленте машины Тьюринга изображен ее собственный шифр (т. е. шифр таблицы соответствия и исходной конфигурации), записанный в алфавите машины. Если машина применима к такой конфигурации, то будем называть ее самоприменимой, в противном случае—несамоприменимой.
Тогда проблема распознавания самоприменимости состоит в следующем: по любому заданному шифру установить, к какому классу относится машина, зашифрованная им, — к классу самоприменимых или несамоприменимых?
Оказывается, можно доказать следующую теорему (6). Проблема распознавания самоприменимости алгоритмически неразрешима.
Доказательство. Предположим, напротив, что такая машина М существует. Тогда в М всякий самоприменимый шифр перерабатывается в какой-то символ v (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамоприменимый шифр — в символ т (имеющий смысл отрицательного ответа на поставленный вопрос).
В таком случае можно было бы построить и такую машину М1, которая по-прежнему перерабатывает несамоприменймые шифры в t , в то время как к самоприменимым шифрам М1 уже не применима. Этого можно добиться путем такого изменения схемы машины (таблицы соответствия) M, чтобы после появления символа v вместо остановки машина стала бы неограниченно повторять этот же символ.
Итак, М1 применима ко всякому несамоприменимому шифру (вырабатывая при этом символ t ) и не применима к самоприменимым шифрам. Однако это приводит к противоречию.
Действительно:
1) пусть машина М1 самоприменима, тогда она применима к своему шифру M1′ и перерабатывает его в символ t , но появление этого символа как раз и должно означать, что машина несамоприменима;
2) пусть M1 несамоприменима, тогда она применима к M1′, что должно означать, что М1 самоприменима.
Полученное противоречие доказывает теорему, т. е. наше предположение о машине М неверно.
Поскольку различных слов в любом исчислении может быть бесчисленное множество, то фактически здесь имеется бесконечная серия однотипных задач. Требуется найти алгоритм, распознающий эквивалентность или неэквивалентность любой пары слов.
Проблема эквивалентности слов для ассоциативных исчислений была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления
и для любой пары слов в нем позволил установить, эквивалентны эти слова или нет.
В 1946 и 1947 гг. А. А. Марков и Э. Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.
В 1955 г. советский математик П. С. Новиков доказал алгоритмическую неразрешимость проблемы распознаваемости слов для ассоциативных исчислений специального вида называемых теорией групп.