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

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

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

Таким образом, задачи (проблемы) можно разделить на алгоритмически разрешимые и алгоритмически неразрешимые.

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

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

Таким образом, возникает задача: как узнать, является ли самоприменимым тот или иной алгоритм.

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

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

Рекомендуемая литература

1. Брауэр В. Введение в теорию конечных автоматов. -М.: Радио и связь, 1987.

2. Гинзбург С. Математическая теория контекстно-свободных языков. - М.: Мир, 1970.

3. Гросс М., Лантен А. Теория формальных грамматик.- М.: Мир, 1971.

Контрольные задания для СРС (тема 1) [1, 2, 7]

1. Способы представления машины Тьюринга

2. Операции над машинами Тьюринга

Дата добавления: 2015-07-26; просмотров: 335; Нарушение авторских прав

Мы поможем в написании ваших работ!