СВОДИМОСТЬ

отношение между понятиями (предложениями, задачами, теориями и др.), играющее важнейшую роль в логике и математике; означает возможность редукции (свед?ния) одного понятия к другому (аналогично для предложений, задач и др.). Интуитивное понимание термина "С." целиком соответствует его этимологии; напр., задача А, по определению, сводится к задаче В, если из решения задачи В может быть получено решение задачи А. Для того же, чтобы этому пониманию придать вполне точный смысл, необходима точная характеристика допустимых методов свед?ния, требующая привлечения понятий теории алгоритмов. Понятие а л г о р и т м и ч е с к о й С. стало играть особенно важную роль в математической логике со времени получения первых результатов, относящихся к разрешения проблеме (А. Черч, Э. Пост, ?. Марков и др.). В качестве примера несколько другого уточнения понятия С. может служить предложенное сов. математиком Ю. Т. Медведевым понятие С. массовых проблем. Пусть решение к.-л. матем. задачи А связано с выполнением бесконечной серии элементарных актов, подчиненных нек-рому (зависящему от А) условию, причем каждый элементарный акт любой серии можно эффективно охарактеризовать нек-рым натуральным числом. Каждая такая серия Sa={a1, а2, ...} дает вариант решения, а совокупность всех Sa образует полностью определяющий А класс ?A. Задачи такого рода Медведев и наз. массовыми проблемами. Всякой серии Sa соответствует такая функция f(x), что для любого натурального числа n натуральное число f(n) характеризует акт аn; классу РA соответствует класс {f} таких "разрешающих функций" массовой проблемы А, полностью ее определяющий: А = {f}. Обратно, всякий класс А, состоящий из функций от натурального аргумента с натуральными значениями, определяет массовую проблему: построить функцию f?A. Если А – проблема разрешения, то соответств. класс состоит из одного элемента. Массовая проблема, для к-рой существует общекурсивная функция (см. Рекурсивные функции и предикаты) f?A, наз. разрешимой, в противном случае – неразрешимой. Наконец, массовая проблема В = {g}, по определению, сводится к массовой проблеме А = {f}, если существует такой частично-рекурсивный оператор R, что для всех f?A Rf = g?В (где g зависит от f). Это понятие С. позволяет частично упорядочить (см. Порядка отношение) класс массовых проблем при помощи естественно вводимого понятия степени трудности (это делается обычным способом разбиения на классы эквивалентности, каждый из к-рых содержит взаимно сводимые массовые проблемы, причем сами эти классы и наз. степенями трудности). Каждой логико-арифметич. формуле можно сопоставить массовую проблему, степень трудности к-рой характеризует "степень неконструктивности" утверждаемого этой формулой высказывания (в частности, конструктивно истинным формулам соответствуют разрешимые массовые проблемы, и обратно). Понятие С. (как в естественном, интуитивном, так и в алгоритмич. смысле), прилагаемое к практически неогранич. кругу проблем науки и мышления вообще, играет основополагающую методологич. роль в каждой области знания. Так, напр., идея дедуктивного построения теории, при к-ром понятия теории определяются исходя из перечня первичных (исходных, неопределяемых) терминов, а предложения выводятся из аксиом, по существу целиком базируется на концепции С. [см. подробнее Метод аксиоматический, Вывод (в математич. логике), Определение]. Аналогично, в эмпирич. науках постоянно (хотя и не всегда в явной форме) пользуются идеей С. к данным наблюдения и опыта. Можно, конечно, говорить и о промежуточных, "эмпирико- дедуктивных" модификациях С. О т.н. аксиомах сводимости – см. Типов теория. Лит. см. при статьях Алгоритм, Массовая проблема. Ю. Гастев. Москва.