Набор индексов (вычислимость)

В вычислимости теории индексные множества описывают классы вычислимых функций ; в частности, они дают все индексы функций определенного класса в соответствии с фиксированной гёделевой нумерацией частично вычислимых функций.

Определение

Позволять $\varphi _{e}$ быть вычислимым перечислением всех частично вычислимых функций и $W_{e}$ — вычислимое перечисление всех в.п. множеств .

Позволять ${\mathcal {A}}$ — класс частично вычислимых функций. Если $A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}$ затем $A$ это индексов набор ${\mathcal {A}}$ . В общем $A$ является набором индексов, если для каждого $x,y\in \mathbb {N}$ с $\varphi _{x}\simeq \varphi _{y}$ (т.е. они индексируют одну и ту же функцию), мы имеем $x\in A\leftrightarrow y\in A$ . Интуитивно понятно, что это наборы натуральных чисел, которые мы описываем только со ссылкой на функции, которые они индексируют.

Наборы индексов и теорема Райса

Большинство наборов индексов невычислимы, за исключением двух тривиальных исключений. Об этом говорится в теореме Райса :

Позволять ${\mathcal {C}}$ быть классом частично вычислимых функций со своим набором индексов $C$ . Затем $C$ вычислимо тогда и только тогда, когда $C$ пусто или $C$ это все из $\mathbb {N}$ .

Теорема Райса гласит: «Любое нетривиальное свойство частично вычислимых функций неразрешимо». ^[1]

Полнота в арифметической иерархии

Наборы индексов предоставляют множество примеров наборов, которые являются полными на некотором уровне арифметической иерархии . Здесь мы говорим $\Sigma _{n}$ набор $A$ является $\Sigma _{n}$ -полный , если для каждого $\Sigma _{n}$ набор $B$ , имеет место m-редукция от $B$ к $A$ . $\Pi _{n}$ -полнота определяется аналогично. Вот несколько примеров: ^[2]

$\mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}$ является $\Pi _{1}$ -полный.
$\mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}$ является $\Sigma _{2}$ -полный.
$\mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}$ является $\Pi _{2}$ -полный.
$\mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}$ является $\Pi _{2}$ -полный.
$\mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}$ является $\Pi _{2}$ -полный.
$\mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}$ является $\Sigma _{3}$ -полный.
$\mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}$ является $\Sigma _{3}$ -полный.
$\mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}$ является $\Sigma _{3}$ -полный.
$\mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}$ является $\Sigma _{4}$ -полный, где $\mathrm {HP}$ это проблема остановки .

Эмпирически, если «наиболее очевидное» определение множества $A$ является $\Sigma _{n}$ [отв. $\Pi _{n}$ ], мы обычно можем показать, что $A$ является $\Sigma _{n}$ -полный [отв. $\Pi _{n}$ -полный].

Примечания

^ Одифредди, П.Г. Классическая теория рекурсии, Том 1 . ; стр. 151
^ Соаре, Роберт И. (2016), «Сводимость по Тьюрингу» , Вычислимость по Тьюрингу , Теория и приложения вычислимости, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 51–78, doi : 10.1007/978-3-642-31933-4_3 , ISBN 978-3-642-31932-7 , получено 21 апреля 2021 г.

Ссылки

Одифредди, П.Г. (1992). Классическая теория рекурсии, Том 1 . Эльзевир. п. 668. ИСБН 0-444-89483-7 .
Роджерс младший, Хартли (1987). Теория рекурсивных функций и эффективная вычислимость . МТИ Пресс. п. 482. ИСБН 0-262-68052-1 .

[odifreddi-1] Одифредди, П.Г. Классическая теория рекурсии, Том 1 . ; стр. 151

[2] Соаре, Роберт И. (2016), «Сводимость по Тьюрингу» , Вычислимость по Тьюрингу , Теория и приложения вычислимости, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 51–78, doi : 10.1007/978-3-642-31933-4_3 , ISBN 978-3-642-31932-7 , получено 21 апреля 2021 г.

[1]

[2]