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

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

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

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

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

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

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

Примеры

Диофантовость

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

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

См. также

Примечания

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

Литература

  • Роджерс Х. = Theory of recursive functions and effective computability : [пер. с англ. ] / под ред. В. А. Успенского : пер. с англ. В. А. Душского, М. И. Кановича, Е. Ю. Ногиной. — М. : Мир, 1972.
Источник —

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