Гуманитарные технологии Аналитический портал • ISSN 2310-1792

Алгоритмическая неразрешимость

Наиме­нова­ние: Алгоритмическая неразрешимость.
Опреде­ление: Алгоритмическая неразрешимость — это свойство некоторых классов корректно поставленных задач, допускающих применение алгоритмов, которое состоит в том, что задачи каждого из этих классов в принципе не имеют какого-либо общего, универсального алгоритма решения, объединяющего этот класс.
Текст: Авторы: А. Н. Поддьяков. Подготовка элект­рон­ной публи­ка­ции и общая редакция: Центр гумани­тарных техно­логий. Инфор­ма­ция на этой стра­нице пери­оди­чески обнов­ля­ется. Послед­няя редакция: 07.12.2017.

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

Алгоритмически неразрешимыми являются, например, проблема распознавания (закончит ли свою работу или же «зависнет» в бесконечном цикле произвольно выбранная программа действий алгоритмического типа, причём не только компьютерная, но и реализуемая человеком по алгоритмическому типу); проблема эквивалентности программ (не существует универсального алгоритма, позволяющего установить эту эквивалентность; проблема тождества двух математических выражений; проблема распознавания того, можно ли из имеющихся автоматов собрать заданный автомат; а также множество других проблем, относящихся к топологии, к теории групп и к другим областям.

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

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

Библио­графия:
  1. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. — М., 1979.
  2. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. — М., 1980.
  3. Игошин В. И. Математическая логика и теория алгоритмов. — 2-е издание. — М., 2008.
  4. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 3-е издание. — М., 2013.
  5. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. — М., 1972.
  6. Теория рекурсий. — В книге: Справочная книга по математической логике. — М., 1982.
  7. Успенский В. Α., Семёнов А. Л. Теория алгоритмов: основные открытия и приложения. — М., 1987.
Источник: Алгоритмическая неразрешимость. Гуманитарная энциклопедия [Электронный ресурс] // Центр гуманитарных технологий, 2010–2017 (последняя редакция: 07.12.2017). URL: http://gtmarket.ru/concepts/7335
Авторы статьи: © А. Н. Поддьяков. Подготовка электронной публикации и общая редакция: Центр гуманитарных технологий.