Рекурсивно перечисляемый набор

редактировать

концепция математической логики

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

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

Или, что эквивалентно,

Существует алгоритм , который перечисляет элементы S. Это означает, что его вывод - это просто список членов S: s 1, s 2, s 3,.... При необходимости этот алгоритм может работать бесконечно.

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

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

Contents

1 Формальное определение
2 Эквивалентные формулы
3 Примеры
4 Свойства
5 Примечания
6 Ссылки

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

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

Эквивалентные формулировки

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

Полуразрешимость:

Множество S рекурсивно перечислимо. То есть S является областью (совмещением) частично рекурсивной функции.
Существует частично рекурсивная функция f такая, что:

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

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

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

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

Диофантова:

Существует многочлен p с целыми коэффициентами и переменными x, a, b, c, d, e, f, g, h, i с переходом по натуральным числам, таким что

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

x \ в 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,...»

Примеры

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

Свойства

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

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

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

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

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

Замечания

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

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

Ссылки

Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость, MIT Press. ISBN 0-262-68052-1 ; ISBN 0-07-053522-1.
Soare, R. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7.
Соар, Роберт И. Рекурсивно перечислимые множества и степени. Бык. Амер. Математика. Soc. 84 (1978), нет. 6, 1149–1181.