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

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

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

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

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

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

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

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

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

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

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

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

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

• Множество S вычислимо перечислимо. То есть S — это область определения (совместный диапазон) частично вычислимой функции.
• Множество S есть (имеется в виду арифметическая иерархия ). ^[1] ${\displaystyle \Sigma _{1}^{0}}$
• Существует частично вычислимая функция f такая, что:
  $${\displaystyle 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 , пробегающими натуральные числа, такой, что
  $${\displaystyle 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 содержит ровно неотрицательные числа в своем диапазоне.

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

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

Примеры

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

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

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

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

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

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

Примечания

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

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

Смотрите также

• РЭ (сложность)
• Рекурсивно перечислимый язык
• Арифметическая иерархия

Рекомендации

1. Дауни, Родни Г.; Хиршфельдт, Денис Р. (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 .  
• Соаре, Р. Рекурсивно перечислимые множества и степени. Перспективы математической логики. Springer-Verlag , Берлин, 1987. ISBN 3-540-15299-7 . 
• Соаре, Роберт И. Рекурсивно перечислимые множества и степени. Бык. амер. Математика. Соц. 84 (1978), вып. 6, 1149–1181.