Приоритета Метод

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

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

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

В. А. Душский.