Наука
Регистрация
Advertisement

Перечислимое множество — множество конструктивных объектов (например, натуральных чисел), элементы которого могут быть эффективно перенумерованы (возможно, с повторениями).

Варианты определения[]

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

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

Литература[]

  • Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972.
Advertisement