Энциклопедия эпистемологии и философии науки

АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ

АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ— важнейшее свойство некоторых классов корректно поставленных задач, допускающих применениеалгоритмов.Оно состит в том, что задачи каждого из этих классов в принципе не имеют какого-либо общего, универсального алгоритма решения, объединяющего этот класс. Несмотря на полную однотипность условий и требований, здесь, как ни парадоксально, принципиально невозможна однотипность метода решения. А. н. не означает неразрешимости тех или иных единичных проблем данного класса — часть из них может иметь свои решения. Но в целом данный класс задач не имеет ни общего универсального алгоритма решения, ни ветвящегося алгоритма полного разбиения класса на подклассы, к каждому из которых был бы применим свой специфический алгоритм.
Алгоритмически неразрешимыми являются, напр., проблемараспознавания:закончит ли свою работу (остановится ли) или же «зависнет» в бесконечном цикле произвольно выбранная программа действий алгоритмического типа (не только компьютерная, но и реализуемая человеком по алгоритмическому типу); проблема эквивалентности программ (нет универсального алгоритма, позволяющего установить эту эквивалентность); проблематождествадвух математических выражений; проблема распознавания того, можно ли из имеющихся автоматов собрать заданный автомат; а также множество других проблем, относящихся к топологии, к теории групп и к другим областям.
А.н. как невозможность обобщенной системы точных предписаний по решению задач одного и того же типа имеет принципиальное значение для психологии мышления, обучения и теории познания. В частности, из нее вытекает, что основные компоненты деятельности человека (планирование, выполнение, контроль результатов, коррекция) не могут быть построены на алгоритмической основе, хотя и могут включать в качестве вспомогательных те или иные алгоритмические процедуры. Решение задачи, относящейся к типу алгоритмически неразрешимых, с неизбежностью включает неалгоритмизуемые компоненты и требуеттворчества:способ ее решения не выводится из более общего известного типового метода, а изобретается. Успех здесь не может быть гарантирован на 100% никакими методами (в отличие от ситуации с алгоритмически разрешимыми задачами).
Таким образом, А. н. как объективная невозможность универсальных точных предписаний, однозначно приводящих к заданному результату, означает свободу выбора и объективную необходимость творческого поиска.
А.Н. Поддьяков

  1. алгоритмическая неразрешимость—англ. algorithmic unsolvability важнейшее свойство некоторых классов корректно поставленных задач допускающих применение алгоритмов состоящее в том что задачи каждого из...Большая психологическая энциклопедия
  2. алгоритмическая неразрешимость—АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ англ. algorithmic unsolvability важнейшее свойство некоторых классов корректно поставленных задач допускающих применение алгоритмов состоя...Большой психологический словарь
  3. алгоритмическая неразрешимость—п.п. алгоритмдк шешлместк...Орысша-қазақша салааралық терминологиялық сөздік
  4. алгоритмическая неразрешимость—algorithmic undecidability...Русско-английский словарь по электронике
  5. алгоритмическая неразрешимость—алгарытмчная неразвязальнасць...Русско-белорусский математический словарь
  6. алгоритмическая неразрешимость—Алгоритмическая неразрешимость Алгоритмическая неразрешимость в математической логике свойство математической задачи заключающееся в отсутствии алгоритма ее решения. См...Финансовый словарь