Массовая Проблема

Алгоритмическая проблем а,- проблема нахождения алгоритма для решения бесконечной серии однотипных задач, зависящих от нек-рого параметра. Простейшие примеры М. п.: сложить два данных десятичных числа, умножить два данных числа, проверить, является данное целое число простым или нет, найти производную данной функции, разложить данную функцию в степенной ряд и т. д. Если искомый алгоритм не существует, то говорят, что рассматриваемая М. п. неразрешима. Проблему нахождения алгоритма, решающего данную М. п., иногда называют проблемой разрешимости. Этот несколько неудачный термин исторически впервые появился в связи с проблемой распознавания выводимости формул в классическом исчислении предикатов. Вообще же говоря, под проблемой разрешимости данной М. п. естественно считать вопрос о том, разрешима или нет эта M. п., т. е. существует или нет искомый алгоритм. См. также Алгоритмическая проблема. с. И. Адян.