ИСЧИСЛЕНИЕ ЗАДАЧ, теория задач

— теория, представляющая собой особое истолкование языка логики предикатов. Создана А. Н. Колмогоровым в 1932 г. Логические связки и т. д. служат, при их обычном истолковании, для образования новых утверждений из заданных. Идея И. з. состоит в том, что эти же связки можно понимать как символы операций над объектами, отличными от логнч. утверждений. В качестве таких новых объектов предлагается рассматривать задачи. Если А и В — достаточно четко поставленные задачи (как, напр., в случае геом. задач на построение с помощью циркуля и линейки), то ясен также смысл следующей задачи: «решить обе задачи А и 5». По аналогии с логикой эту задачу естественно обозначить через

. Задача А у В ставится так: «назвать одну из задач А, В и дать ее решение». Задача А В: «свести решение задачи В к решению задачи А», т. е. «указать метод решения В в предположении, что решение А дано». Наконец, есть задача: «установить невозможность решения задачи А». Можно также определить операции над задачами, соответствующие логическим кванторам общности и существования. Произвольная логич. превращается в некоторую задачу, если переменные заменить конкретными задачами А, В, С и последовательно осуществить все операции. Может оказаться, что для данной ф-лы существует общий метод решения всех так возникающих задач. В этом случае истинной ф-лой И. з. Напр., а истинна, так как для любых задач А, В и С можно решить . Последнее следует из того, что при наличии решения в силу определения . В известны как решение А, так и решение В, поэтому искомый метод сведения А к состоит в простом отбрасывании информации, относящейся к В. А. Н. Колмогоров показал, что все аксиомы интуиционистского исчисления предикатов истинны в упомянутом смысле, и что применение правил вывода этого исчисления сохраняет это свойство. Поэтому каждая интуиционистски выводимая ф-ла истинна. Вместе с тем, сразу видно, что выражающую исключенного третьего закон (она невыводима интуиционистски, хотя выводима в классической логике), нет оснований считать истинной. Действительно, из истинности а у а следовало бы, напр., что мы в состоянии решить задачу , где А — задача доказательства гипотезы Римана. Но в силу определения операций означало бы, по меньшей мере, что мы знаем, справедлива или ложна эта гипотеза.

И. з. было предложено в качестве основы для интерпретации интуиционистской логики. Эта роль И. з. связана с возможностью рассматривать логнч. утверждения как задачи частного вида. Но значение И. з. не ограничивается философией интуиционизма. Идея А. Н. Колмогорова получила многочисленные применения и развитие, причем уточнялось расплывчатое понятие задачи, а также видоизменялось понятие истинности. Реализуемость в смысле Клини, первое по времени понятие истинности для логико-арифм. ф-л, основанное на идее вычислимости, полностью соответствует духу И. з. Теория задач играет определенную роль в построении различных вариантов конструктивной математики (см. Конструктивное направление в математике). С неконструктивной, теоретико-множественной точки зрения, алгоритм, проблемы самого общего вида образуют (при подходящем определении операций над ними) некоторое И. з. Исследовалось исчисление финитных задач, для построения которого достаточно финитных средств. Интерпретация арифметики, предложенная Гёделем (распространенная впоследствии на анализфактически основана на одном варианте теории задач, более удовлетворительном, чем теория реализуемости Клини. Построение автором «исчисления локально-финитных алгоритмических проблем» является попыткой интерпретации арифметики минимальными средствами. Можно предполагать, что теоретико-задачный метод всегда будет играть существенную роль при разработке и обосновании формализованных теорий.

Ю. Т. Медведев.