Прямой Пересчет

Пересчет элементов нек-рого множества натуральных чисел в порядке их возрастания. Точнее, .П. п. множества Анатуральных чисел есть строго возрастающая функция натурального аргумента, область значений к-рой совпадает с А. В теории алгоритмов рекурсивность и скорость возрастания П. п. множества являются его важными характеристиками. Напр., общерекурсивность (примитивная рекурсивность) П. п. бесконечного множества эквивалентна разрешимости (примитивно рекурсивной разрешимости) этого множества. Множества натуральных чисел, П. п. к-рых но мажорируются никакой общерекурсивной функцией, наз. гипериммунными, они играют существенную роль в теории табличной сводимости. Лит.: [1] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [2] Роджерс X., Теория рекурсивных Функций и эффективная вычислимость, пер. с англ., М., 1972. С. Н. Артемов.