" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

ПРЯМОЙ ПЕРЕСЧЕТ

Значение ПРЯМОЙ ПЕРЕСЧЕТ в математической энциклопедии:

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

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

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