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

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

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

С. Н. Артемов.

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

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

1977—1985