Рекурсивно перечислимый набор - Recursively enumerable set

В теория вычислимости, традиционно называемый теорией рекурсии, множество S из натуральные числа называется рекурсивно перечислимый, вычислимо перечислимый, полуразрешимый, доказуемо или же Узнаваемый по Тьюрингу если:

Существует алгоритм такой, что набор входных чисел, для которых алгоритм останавливается, точно S.

Или, что то же самое,

Существует алгоритм, который перечисляет члены S. Это означает, что его вывод представляет собой просто список всех членов S: s₁, s₂, s₃, .... Если S бесконечно, этот алгоритм будет работать вечно.

Первое условие подсказывает, почему термин полуразрешимый иногда используется; второй предлагает почему вычислимо перечислимый используется. Сокращения r.e. и c.e. часто используются, даже в печатном виде, вместо полной фразы.

В теория сложности вычислений, то класс сложности содержащий все рекурсивно перечислимые множества, RE. В теории рекурсии решетка г. э. под включением обозначается ${ displaystyle { mathcal {E}}}$ .

Формальное определение

Множество S натуральных чисел называется рекурсивно перечислимый если есть частичная рекурсивная функция чей домен точно S, что означает, что функция определена тогда и только тогда, когда ее вход является членом S.

Эквивалентные составы

Ниже приведены все эквивалентные свойства набора S натуральных чисел:

Полурастворимость:

Набор S рекурсивно перечислимо. То есть, S является областью (совмещенным диапазоном) частично рекурсивной функции.
Есть частичная рекурсивная функция ж такой, что:

{ displaystyle f (x) = left {{ begin {matrix} 1 & { mbox {if}} x in S { mbox {undefined / не останавливается}} & { mbox { if}} x notin S end {matrix}} right.}

Перечислимость:

Набор S - это диапазон частичной рекурсивной функции.
Набор S - это диапазон полной рекурсивной функции или пустой. Если S бесконечно, функция может быть выбрана инъективный.
Набор S это диапазон примитивная рекурсивная функция или пусто. Даже если S бесконечно, в этом случае может потребоваться повтор значений.

Диофантин:

Есть многочлен п с целыми коэффициентами и переменными Икс, а, б, c, d, е, ж, грамм, час, я начиная с натуральных чисел так, что

{ Displaystyle х в S Leftrightarrow существует a, b, c, d, e, f, g, h, i (p (x, a, b, c, d, e, f, g, h, i) = 0).}

(Число связанных переменных в этом определении является наиболее известным до сих пор; возможно, меньшее число может быть использовано для определения всех диофантовых множеств.)

Существует многочлен от целых чисел к целым таким, что множество S содержит ровно неотрицательные числа из своего диапазона.

Эквивалентность полуразрешимости и перечислимости может быть получена методом ласточкин хвост.

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

Рекурсивное перечисление набора всех машин Тьюринга, останавливающихся на фиксированном входе: моделируйте все машины Тьюринга (перечисленные на вертикальной оси) шаг за шагом (горизонтальная ось), используя показанное планирование диагонализации. Если машина отключится, выведите ее номер. Таким образом, в конечном итоге печатается номер каждой оконечной машины. В этом примере алгоритм печатает «9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ...»

Примеры

Каждый рекурсивный набор рекурсивно перечислим, но неверно, что каждый рекурсивно перечислимый набор является рекурсивным. Для рекурсивных наборов алгоритм также должен сказать, является ли вход нет в наборе - этого не требуется для рекурсивно перечислимых множеств.
А рекурсивно перечислимый язык рекурсивно перечислимое подмножество формальный язык.
Множество всех доказуемых предложений в эффективно представленной аксиоматической системе является рекурсивно перечислимым множеством.
Теорема Матиясевича утверждает, что каждое рекурсивно перечислимое множество является Диофантовый набор (тривиально верно обратное).
В простые наборы рекурсивно перечислимы, но не рекурсивны.
В творческие наборы рекурсивно перечислимы, но не рекурсивны.
Любой производительный набор является нет рекурсивно перечислимый.
Учитывая Гёделевская нумерация ${ displaystyle phi}$ вычислимых функций множество ${ displaystyle { langle i, x rangle mid phi _ {i} (x) downarrow }}$ (куда ${ Displaystyle langle я, х rangle}$ это Функция сопряжения Кантора и ${ Displaystyle phi _ {я} (х) вниз}$ указывает ${ Displaystyle phi _ {я} (х)}$ определено) рекурсивно перечислимо (см. рисунок для фиксированного Икс). Этот набор кодирует проблема остановки поскольку он описывает входные параметры, для которых каждый Машина Тьюринга остановки.
Учитывая гёделевскую нумерацию ${ displaystyle phi}$ вычислимых функций множество ${ displaystyle lbrace left langle x, y, z right rangle mid phi _ {x} (y) = z rbrace}$ рекурсивно перечислимо. Этот набор кодирует проблему определения значения функции.
Учитывая частичную функцию ж из натуральных чисел в натуральные числа, ж является частично рекурсивной функцией тогда и только тогда, когда график ж, то есть множество всех пар ${ Displaystyle langle х, е (х) rangle}$ такой, что f (x) определен, рекурсивно перечислим.

Характеристики

Если А и B рекурсивно перечислимые множества, то А ∩ B, А ∪ B и А × B (упорядоченная пара натуральных чисел отображается в одно натуральное число с Функция сопряжения Кантора ) рекурсивно перечислимые множества. В прообраз рекурсивно перечислимого множества при частично рекурсивной функции является рекурсивно перечислимым множеством.

Набор рекурсивно перечислим тогда и только тогда, когда он находится на уровне ${ displaystyle Sigma _ {1} ^ {0}}$ из арифметическая иерархия.

Множество ${ displaystyle T}$ называется ко-рекурсивно перечислимый или же основной. если это дополнять ${ Displaystyle mathbb {N} setminus T}$ рекурсивно перечислимо. Эквивалентно, набор является co-r.e. если и только если он на уровне ${ displaystyle Pi _ {1} ^ {0}}$ арифметической иерархии. Класс сложности ко-рекурсивно перечислимых множеств обозначается co-RE.

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

Некоторые пары рекурсивно перечислимых множеств являются эффективно отделяемый а некоторые нет.

Замечания

Согласно Тезис Черча – Тьюринга, любая эффективно вычисляемая функция вычисляется Машина Тьюринга, а значит, и множество S рекурсивно перечислим тогда и только тогда, когда есть некоторые алгоритм что дает перечисление S. Однако это не может считаться формальным определением, потому что тезис Черча – Тьюринга является скорее неформальной гипотезой, чем формальной аксиомой.

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

Математическая логика
Общий	Формальный язык Правило формирования Формальное доказательство Формальная семантика Правильная формула Набор Элемент Учебный класс Классическая логика Аксиома Правило вывода Связь Теорема Логическое следствие Теория типов Символ Синтаксис Теория
Системы	Формальная система Дедуктивная система Аксиоматическая система Системы гильбертовского стиля Естественный вычет Последовательное исчисление
Традиционная логика	Предложение Вывод Аргумент Срок действия Силлогизм Площадь оппозиции Диаграмма Венна
Исчисление высказываний и Логическая логика	Логические функции Исчисление высказываний Пропозициональная формула Логические связки Таблицы истинности Многозначная логика
Логика предикатов	Первый заказ Квантификаторы Предикат Второго порядка Монадическое исчисление предикатов
Наивная теория множеств	Набор Пустой набор Элемент Перечисление Расширяемость Конечный набор Бесконечный набор Подмножество Набор мощности Счетный набор Бесчисленное множество Рекурсивный набор Домен Codomain Изображение карта Функция Связь Упорядоченная пара
Теория множеств	Основы математики Теория множеств Цермело – Френкеля Аксиома выбора Общая теория множеств Теория множеств Крипке – Платека. Теория множеств фон Неймана – Бернейса – Гёделя. Теория множеств Морса – Келли Теория множеств Тарского – Гротендика
Теория моделей	Модель Интерпретация Нестандартная модель Теория конечных моделей Ценность правды Срок действия
Теория доказательств	Формальное доказательство Дедуктивная система Формальная система Теорема Логическое следствие Правило вывода Синтаксис
Вычислимость теория	Рекурсия Рекурсивный набор Рекурсивно перечислимый набор Проблема решения Тезис Черча – Тьюринга Вычислимая функция Примитивная рекурсивная функция