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

метод, применяемый в рекурсивной теории множеств для построения просто устроенных с рекурсивной точки зрения (в простейших случаях рекурсивно перечислимых) множеств (функций, нумераций и т. п.), удовлетворяющих бесконечной системе условий определенного типа. Специфика допустимых условий такова, что для того чтобы удовлетворить отдельному условию из данной системы, обычно бывает достаточно, чтобы в строящееся множество был включен определенный (зависящий от рассматриваемого условия) элемент. Однако на каждом этапе построения (представляющего собой нек-рый вычислительный процесс, чем и обеспечивается рекурсивная простота строения искомого объекта) каждое из условий системы (к-рое определяется, вообще говоря, бесконечным множеством конструктивных объектов) представлено нек-рой своей конечной аппроксимацией. Включение в строящееся множество элемента, обеспечивающего выполнение аппроксимации j-го условия, еще не дает гарантии, что тем самым будет удовлетворено само j-е условие. П. м. позволяет в известных случаях обходить это препятствие. С этой целью j-му условию данной системы, j=1, 2, 3, ..., в процессе построения ставится в соответствие натуральное число, являющееся кандидатом на роль элемента, включение к-рого в строящееся множество удовлетворяет j-му условию; про такой элемент принято говорить, что он помечен маркером (снабженным, возможно, дополнительными индексами). Каждый такой кандидат может в процессе построения заменяться (или, что то же самое, маркер может сдвигаться), но при этом в простейших приоритетных конструкциях сама последовательность, в к-рой выполняются попытки удовлетворить данным условиям, организуется так, что каждый маркер может изменить свое положение лишь конечное число раз, причем в своем заключительном положении он с необходимостью отмечает элемент, гарантирующий выполнение соответствующего условия.

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

Лит.:[1) Роджерс X., теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [2] Sасks G. E., Degrees of unsolvability, Princeton (N.J.), 1963. В. А. Душский.

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

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

1977—1985