«массовая проблема»

мат. mass problem

МА́ССОВАЯ ПРОБЛЕ́МА

бесконечный класс (научных) проблем (задач), охарактеризованный (или могущий быть охарактеризованным) при помощи нек-рого единого эффективно распознаваемого условия. На фигурирующее в этом пояснении понятие проблемы следует смотреть как на объемно-неопределенное, поскольку любая попытка предопределить, какие проблемы могут когда-либо в будущем представлять интерес для к.-л. области знания, неоправданна. В характеристике понятия М. п. существенным является б е с к о н е ч н о с т ь класса проблем, т.к. в применении к конечному классу задач не имеет смысла говорить об общем способе их задания, – этот класс может быть задан простым перечислением условий отд. проблем. Не менее существенным является требование эффективной р а с п о з н а в а е м о с т и того, удовлетворяет ли данная единичная проблема условию, характеризующему М. п., т.к. в противном случае самая постановка вопроса о "решении" М. п. становится неопределенной. Понятие эффективной распознаваемости теснейшим образом связано с уточняющим его понятием алгоритма. Однако понятие "алгоритм" незачем включать в характеристику понятия М. п., поскольку для отнесения к.-л. конкретного класса задач к категории М. п. нужно не п о н я т и е об эффективной распознаваемости, а лишь нек-рое к о н к р е т н о е эффективно распознаваемое условие. Решением М. п. естественно считать нек-рую общую схему предписаний, применяемых к каждой из входящих в М. п. единичных проблем и дающих для каждой такой проблемы ее решение (в том смысле, в каком этот термин применим к задачам данного типа). Т. о., мы приходим к понятию алгоритма, к-рое может быть, в частности, охарактеризовано как решение массовой проблемы. М. п., для к-рой существует решающий ее алгоритм, наз. р а з р е ш и м о й; если же доказано, что такого алгоритма не может быть, то М. п. наз. (алгоритмически) неразрешимой. Неразрешимость М. п. предполагает невозможность н и к а к о г о алгоритма-решения – сам по себе факт отсутствия такого алгоритма, без доказательства его невозможности, свидетельствует лишь о том, что данная М. п. еще не решена, также как не решена ее разрешения проблема.

Понятие М. п. имеет фундаментальное методологич. и гносеологич. значение. Для любой науки характерно стремление перейти от описания единичных фактов и решения единичных задач к формулировке и решению М. п., охватывающих по возможности более широкий класс явлений описываемой в данной науке области действительности. Так, решениями определ. М. п. служат законы физики, в формулировку каждого из к-рых входят, кроме констант (характеризующих М. п. в целом), нек-рые переменные (параметры), каждому конкретному набору значений к-рых соответствует решение конкретной (единичной) проблемы. Иначе говоря, М. п. может быть охарактеризована как "задача с п а р а м е т р о м (п а р а м е т р а м и)"; решение понимаемой т.о. М. п. состоит в указании нек-рого правила (формулы), содержащего эти параметры (в отд. случаях решение может и не зависеть от всех параметров, входящих в формулировку самой М. п., – это означает, что нек-рые параметры излишни, несущественны для постановки М. п., или же – в другой трактовке – что решение данной M. п. может быть отнесено к более широкой М. п.).

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

При характеристике неразрешимых М. п. следует, кроме того, иметь в виду, что часто идет речь лишь о неразрешимости определенными средствами. Так, неразрешимость М. п. решения любого алгебраич. уравнения выше 4-й степени в радикалах или неразрешимость М. п. интегрирования любой элементарной функции в элементарных же функциях свидетельствует по существу не о "неразрешимости" этих М. п., а лишь о недостаточности предполагавшихся вначале (и, конечно, желательных ввиду их относит. простоты) средств решения. В упомянутых двух случаях более мощным (уже дающим возможность решения) средством служит, напр., аппарат теории бесконечных рядов.

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

Сказанное выше о первичном, неопределяемом характере М. п. не исключает того, что для этого понятия (как и для понятия алгоритма) были предложены различные, оказавшиеся весьма плодотворными, уточнения. Характерно, что такого рода уточнения всегда предполагают – как и в случае понятия алгоритма – переход от общенауч. понятия М. п., каким оно выступает до уточнений, к трактовке его как понятия логико-математического.

Напр., понятием M. п. по существу воспользовался Колмогоров в предложенной им интерпретации конструктивной (интуицио-нистской) логики (см. Исчисление задач). Пригодное для этой интерпретации уточнение понятия "проблема" было дано Клини. Другим примером может служить определение, предложенное сов. математиком Ю. Т. Медведевым.

Лит.: Медведев Ю. Т., Степени трудности М. п., "Докл. АН СССР", 1955, т. 104, No4; его же, О понятии М. п., "Успехи матем. наук", 1956, т. 11, вып. 5, с. 231–232. См. также лит. при статьях Алгоритм, Исчисление задач, Конструктивное направление.

Ю. Гастев. Москва.

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

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

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