Вычислимо перечислимый

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

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

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

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

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

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

Формальное определение [ править ]

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

Эквивалентные формулировки [ править ]

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

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

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

${\displaystyle f(x)=\left\{{\begin{matrix}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.}$

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

• Множество 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 содержит в точности неотрицательные числа из своего диапазона.

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

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

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

Примеры [ править ]

• Каждый вычислимый набор вычислимо перечислим, но неверно, что каждый вычислимо перечислимый набор вычислим. Для вычислимых множеств алгоритм также должен сказать, если вход отсутствует в наборе - это не требуется для вычислимо перечислимых множеств.
• Перечислимый языком является вычислимо перечислит подмножество формального языка .
• Множество всех доказуемых предложений в эффективно представленной аксиоматической системе является вычислимо перечислимым множеством.
• Теорема Матиясевича утверждает, что каждое вычислимо перечислимое множество является диофантовым множеством (обратное тривиально верно).
• Эти простые наборы являются вычислимо перечислят , но не вычислит.
• В творческих наборах являются вычислимо перечислят , но не вычислит.
• Ни один продуктивный набор не является исчислимо перечислимым.
• Учитывая гёделевскую нумерацию вычислимых функций, множество (где - функция спаривания Кантора и указывает, что определено) является вычислимо перечислимым (см. Рисунок для фиксированного 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 \lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\rbrace }$
• Учитывая частичную функцию f из натуральных чисел в натуральные числа, f является частично вычислимой функцией тогда и только тогда, когда график f , то есть множество всех пар таких, что f (x) определен, является вычислимо перечислимым.${\displaystyle \langle x,f(x)\rangle }$

Свойства [ править ]

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

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

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

Множество является вычислимой тогда и только тогда , когда обе и дополнение А являются вычислимо перечислим.

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

Замечания [ править ]

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

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

Ссылки [ править ]

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