Викия

Математика

Перечислимое множество

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


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

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

Варианты определенияПравить

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

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

ЛитератураПравить

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


he:קבוצה ניתנת למנייה רקורסיבית

Викия-сеть

Случайная вики