Алгоритмически неразрешимые проблемы

Задачи, для которых доказано, что решающего их алгоритма не существует, называются алгоритмически неразрешимыми.

Существует большое количество задач, являющихся алгоритмически неразрешимыми. То есть речь идет об отсутствии единого алгоритма, решающего данную задачу. При этом вовсе не исключается возможность решения задачи в частных случаях, но различными способами для каждого случая.

Рассмотрим несколько примеров алгоритмически неразрешимых задач.

1 Задача эквивалентности алгоритмов

По двум произвольно заданным алгоритмам определить будут ли они выдавать одинаковые выходные результаты на любых исходных данных.

2 Задача останова машины Тьюринга

Не существует алгоритма, позволяющего по описанию произвольного алгоритма и его исходных данных определить, останавливается ли алгоритм на этих данных или работает бесконечно.

3 Задача эквивалентности двух слов в ассоциативном исчислении

Ассоциативным исчислением называют совокупность всех слов в некотором алфавите вместе с какой-либо конечной системой допустимых подстановок.

Подстановка P ® Q называется ориентированной. Она заключается в замене фрагмента P в слове R фрагментом Q.

Подстановка P — Q называется неориентированной. Она заключается как в замене фрагмента P в слове R фрагментом Q, так и в замене в слове R фрагмента Q фрагментом P.

Пример. R = ‘aabcb’ P = ‘ab’ Q = ‘bcb’

При P ® Q получим: R' = ‘abcbcb’.

При P — Q получим как R' = ‘abcbcb’, так и R'' = ‘aaab’.

Два слова R1 и R2 называются эквивалентными для заданной системы ориентированных подстановок, если от слова R1 можно, применяя конечное число раз подстановки, перейти к слову R2.

Если же подстановки неориентированы, то возможность перехода требуется как от R1 к R2, так и от R2 к R1.

Задача эквивалентности слов в ассоциативном исчислении состоит в следующем: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет.

Задача слов не является надуманной, так как к ней может быть сведена любая известная задача.

Например, рассмотрим задачу поиска пути в лабиринте. Изобразим лабиринт в виде графа, в котором вершинам соответствуют площадки, а ребрам — соединяющие их коридоры. Каждой площадке или вершине графа сопоставим некоторое слово. Каждому коридору или ребру xixj сопоставим неориентированную подстановку, переводящую слово, соответствующее xi, в слово, соответствующее xj.

Например, если вершине x1 соответствует слово ‘xypt’, а смежной вершине x2 — слово ‘xyqt’, то неориентированная подстановка будет иметь вид:

‘p’ — ‘q’.

Задача слов решена для некоторых частных случаев. Например, пусть даны алфавит {x, y, z, p, q} и система неориентированных подстановок:

xz — zx, xp — px, yz — zy, yp — py, xyxz — xyxzq, qzx — xq, qpy — yq.

Спрашивается, эквивалентны ли в данном ассоциативном исчислении слова: xyxxzp и xzypxp?

Ответ: нет, не эквивалентны, так как в первом слове нечетное число букв x, а во втором — четное; система же подстановок сохраняет четность или нечетность букв x в словах.

В общем же случае задача слов алгоритмически неразрешима.

4 Задача распознавания выводимости

С задачей эквивалентности двух слов в ассоциативном исчислении тесно связана задача распознавания выводимости, которая является одной из важнейших задач математической логики.

Задача распознавания выводимости состоит в следующем:

для любых двух слов (формул) S и T в логическом исчислении определить выводима ли формула T из формулы S.

Эта задача также алгоритмически неразрешима.

Список литературы

1. Теория алгоритмов Методическое пособие по дисциплине «Математическая логика и теория алгоритмов» / В.П. Битюцкий, Н.В. Папуловская. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006, с.
«Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча.

2. «Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.» (из стандарта специальности ВМКСС, дисциплина «Математическая логика и теория алгоритмов).