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

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

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

• Существует алгоритм , такой что набор входных чисел, на которых алгоритм останавливается, равен в точности 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 (с упорядоченной парой натуральных чисел, отображенной в одно натуральное число с помощью функции спаривания Кантора ) — вычислимо перечислимые множества. Прообраз вычислимо перечислимого множества при частично вычислимой функции — это вычислимо перечислимое множество.

Множество называется co-computably-enumerable или co-ce , если его дополнение вычислимо перечислимо. Эквивалентно, множество является co-re тогда и только тогда, когда оно находится на уровне арифметической иерархии. Класс сложности co-computably-enumerable множеств обозначается co-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 . 
• Соаре, Роберт И. Рекурсивно перечислимые множества и степени. Bull. Amer. Math. Soc. 84 (1978), № 6, 1149–1181.