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

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

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

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

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

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

В теории сложности вычислений , то класс сложности , содержащий все рекурсивно перечислимых множеств 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-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.