Вычислимо перечислимое множество

В теории вычислимости множество S называется натуральных чисел вычислимо перечислимым (ce) , рекурсивно перечислимым (re) , полуразрешимым , частично разрешимым , перечислимым , доказуемым или распознаваемым по Тьюрингу , если:

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

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

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

Первое условие позволяет понять, почему термин «полуразрешимый» иногда используется . Точнее, если число есть в наборе, это можно решить , запустив алгоритм, но если числа нет в наборе, алгоритм работает вечно и никакой информации не возвращается. Множество, которое «вполне разрешимо», — это вычислимое множество . Второе условие подсказывает, почему вычислимо перечислимое используется . Аббревиатуры ce и re часто используются даже в печати вместо полной фразы.

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

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

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

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

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

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

Множество S вычислимо перечислимо. То есть S — это область определения (совместный диапазон) частично вычислимой функции.
Множество S $\Sigma _{1}^{0}$ (имеется в виду арифметическая иерархия ). ^[1]
Существует частично вычислимая функция f такая, что: $f(x)={\begin{cases}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{cases}}$

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

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

Диофантин:

Существует многочлен p с целыми коэффициентами и переменными x , a , b , c , d , e , f , g , h , i, пробегающими по натуральным числам, такой, что $x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).$ (Количество связанных переменных в этом определении на данный момент является наиболее известным; возможно, для определения всех диофантовых множеств можно использовать меньшее число.)
Существует многочлен от целых чисел к целым числам такой, что набор S содержит ровно неотрицательные числа в своем диапазоне.

Эквивалентность полуразрешимости и перечислимости можно получить с помощью техники « ласточкиного хвоста» .

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

Примеры

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

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

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

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

Множество A вычислимо A тогда и только тогда, когда и , и дополнение к A вычислимо перечислимы.

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

Примечания

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

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

См. также

Ссылки

^ Дауни, Родни Г.; Хиршфельдт, Денис Р. (29 октября 2010 г.). Алгоритмическая случайность и сложность . Springer Science & Business Media. п. 23. ISBN 978-0-387-68441-3 .

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

[1] Дауни, Родни Г.; Хиршфельдт, Денис Р. (29 октября 2010 г.). Алгоритмическая случайность и сложность . Springer Science & Business Media. п. 23. ISBN 978-0-387-68441-3 .

[1]