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

Алгоритмическая проблема — это проблема, в которой требуется найти единый метод (алгоритм) для решения бесконечной серии однотипных единичных задач. Такие проблемы называют также массовыми проблемами. Они возникали и решались в различных областях математики на протяжении всей ее истории. .

Математики в начале XX в. столкнулись с тем, что для некоторых массовых проблем не удается подобрать общий алгоритм для их решения. В связи с этим возникла необходимость дать точное определение самому понятию алгоритма. В настоящем параграфе приведем примеры алгоритмически неразрешимых массовых проблем. Сначала в качестве понятия, уточняющего понятие алгоритма, будем использовать понятие машины Тьюринга. Затем рассмотрим проблему алгоритмической разрешимости в рамках общей теории алгоритмов.

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

Поскольку любой алгоритм можно задать конечным описанием (словом) (например, в конечном алфавите знаков, используемых при наборе математических книг), а множество всех конечных слов в фиксированном конечном алфавите счетно, то множество всех алгоритмов счетно. Это означает наличие взаимно-однозначного соответствия между множеством N натуральных чисел и множеством всех алгоритмов, рассматриваемым как подмножество множества Al * всех слов в алфавите А l , выбранном для описания алгоритмов (φ: N → А l * ). Такая функция называется нумерацией алгоритмов. Если φ(n ) = А , то число п называется номером алгоритма А . Из взаимной однозначности отображения φ следует существование обратной функции φ–1, восстанавливающей по описанию алгоритма Апего номер в этой нумерации φ–1(An) = п . Очевидно, что различных нумераций много.

Нумерация всех алгоритмов является одновременно и нумерацией всех вычислимых функций в следующем смысле: номер функции f — это номер некоторого алгоритма, вычисляющего f . Ясно, что в любой нумерации всякая функция будет иметь бесконечное множество различных номеров.

Существование нумераций позволяет работать с алгоритмами как с числами. Это особенно удобно при исследовании алгоритмов над алгоритмами. Отсутствие именно таких алгоритмов часто приводит к алгоритмически неразрешимым проблемам.

Нумерация машин Тьюринга.Опишем теперь более конкретный процесс нумерации всех машин Тьюринга, который используем при построении примера невычислимой по Тьюрингу функции. Будем считать, что для обозначения внутренних состояний машин Тьюринга используются буквы бесконечной последовательности: q 0, q 1, q 2, …, qr, …, а для обозначения букв внешних алфавитов используются буквы последовательности: a 0, a 1, a 2, …, as, ….

Выразим (или, как говорят, закодируем) все символы этих бесконечных последовательностей словами конечного стандартного алфавита {а 0, 1, q , С, П, Л} по следующим правилам:

qi(i = 0, 1, ...) обозначим (закодируем) словом из i + 1 букв q : qq ...q ;

qj(j = 1, 2, ...) обозначим (закодируем) словом из j единиц: 11...1.

В стандартном алфавите программу машины Тьюринга можно записать в виде слова, руководствуясь следующим правилом. Сначала все команды программы переводятся на язык стандартного алфавита, для чего в записях этих команд qiaj→ qlamX , где X Î {С, П, Л}, опускается символ «→», а буквы qi, а j, ql, amзаменяются соответствующими словами стандартного алфавита. Затем полученные слова-команды записываются подряд в любом порядке в виде единого слова.

Например, программа машины Тьюринга, , в этих обозначениях имеет вид: q 1a 0→ q 2a 0П, q 1a 1→ q 1a 1П, q 2a 0→ q 0a 1С, q 2a 1→ q 2a 1П. Опускаем символ «→», заменяем буквы словами стандартного алфавита и в результате получаем следующие слова в стандартном алфавите, кодирующие соответствующие команды: qqa 0qqqa 0П, qqlqql П, qqqa 0q 1C , qqq 1qqq 1П. Выписываем эти слова подряд и получаем слово, кодирующее программу данной машины Тьюринга:

Нетрудно указать алгоритм, позволяющий узнавать, является ли слово в стандартном алфавите программой некоторой машины Тьюринга. Такой алгоритм может, например, состоять в следующем. Нужно анализировать все подслова данного слова, заключенные между всевозможными парами букв из {С, П, Л}. Эти подслова должны иметь следующую структуру: сначала записаны несколько букв q , затем а 0или несколько букв 1, затем снова несколько букв q и, наконец, снова а 0или несколько единиц.

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

Перенумеруем теперь все машины Тьюринга, для чего все слова стандартного алфавита, представляющие собой программы всевозможных машин Тьюринга, расположим в виде фиксированной счетно-бесконечной последовательности, которую составим по такому правилу: сначала выписываются в какой-нибудь фиксированной последовательности все однобуквенные слова: α0, α1, …, αξ, представляющие программы машин Тьюринга (множество таких слов конечно, потому что конечен стандартный алфавит, из букв которого строятся слова), затем выписываются все двухбуквенные слова αξ+1, …, αη, представляющие программы машин Тьюринга (множество таких слов также конечно, потому что конечен стандартный алфавит), затем выписываются трехбуквенные слова и т. д. Получится последовательность программ α0, α1, α2,…, αn, … всех мыслимых машин Тьюринга. Число k будем называть номером машины Тьюринга , если программа этой машины записывается словом αk.