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

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

Что означает термин

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

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

Как устроено

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

При этом отдельные экземпляры могут решаться специальными методами. Частные алгоритмические процедуры не устраняют неразрешимость общего класса, а применимы только к определённым случаям.

Где применяется

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

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

Отличие от близких понятий

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

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