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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество[1]) — множество конструктивных объектов (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым[2]. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню арифметической иерархии (англ.), а корекурсивно перечислимые — уровню

Всякое разрешимое множество является перечислимым.[источник не указан 58 дней] Перечислимое множество является разрешимым, тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножество перечислимого множества может не быть перечислимым (и даже может не быть арифметическим).

Совокупность всех перечислимых подмножеств является счётным множеством, а совокупность всех неперечислимых подмножеств  — несчётным.

Варианты определения[править | править код]

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

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

Примеры[править | править код]

Диофантовость[править | править код]

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

Это означает, в частности, что любое перечислимое множество совпадает с множеством положительных значений, принимаемых при целых параметрах некоторым полиномом с целыми коэффициентами. Данный результат был установлен Юрием Матиясевичем.

См. также[править | править код]

Примечания[править | править код]

  1. А. Е. Пентус, М. Р. Пентус, Математическая теория формальных языков, Лекция 14: Алгоритмические проблемы // Интуит.ру, 09.07.2007
  2. Барвайс, Кеннет Джон. Справочная книга по математической логике. Часть 3: теория рекурсии. — М.: Наука, 1982.

Литература[править | править код]

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