Понятие алгоритмической неразрешимости массовых проблем. Примеры алгоритмических неразрешимых массовых проблем в области информатики

В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому, что его пока не придумали, а потому что он невозможен в принципе.

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

Проблема остановки машины Тьюринга. Машина Тьюринга – это объект, определяемый конечным числом параметров. Все частичные отображения одного конечного множества в другое могут быть эффективным образом перенумерованы.

Поэтому каждой машине Тьюринга можно присвоить номер (натуральное число). Пусть T(n) машина Тьюринга с номером n.

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

Возникает задача: по натуральному числу n определить, остановится или нет машина Тьюринга T(n) запущенная на пустой ленте.

Эта задача алгоритмически неразрешима. То есть не существует автоматической процедуры, для каждого n решающей, останавливается или нет машина T(n).

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

Законы алгебры Буля, их применение для преобразования формул булевых функций.