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

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

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

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

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