Математическая энциклопедия - массовая проблема

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

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

См. также Алгоритмическая проблема. с. И. Адян.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985