Учебное пособие: Теория алгоритмов

Например, рассмотрим задачу поиска пути в лабиринте. Изобразим лабиринт в виде графа, в котором вершинам соответствуют площадки, а ребрам — соединяющие их коридоры. Каждой площадке или вершине графа сопоставим некоторое слово. Каждому коридору или ребру 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.

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

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