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

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

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

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

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

Пусть — класс частично вычислимых функций с индексным множеством . Тогда вычислимо тогда и только тогда, когда пусто или является всеми из .${\displaystyle {\mathcal {C}}}$${\displaystyle С}$${\displaystyle С}$${\displaystyle С}$${\displaystyle С}$${\displaystyle \mathbb {N} }$

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

Индексные наборы предоставляют множество примеров наборов, которые являются полными на некотором уровне арифметической иерархии . Здесь мы говорим, что набор является -полным, если для каждого набора существует m-редукция от до . -полнота определяется аналогично. Вот несколько примеров: ^[2]${\displaystyle \Сигма _{n}}$${\displaystyle А}$${\displaystyle \Сигма _{n}}$${\displaystyle \Сигма _{n}}$${\displaystyle Б}$${\displaystyle Б}$${\displaystyle А}$${\displaystyle \Пи _{n}}$

• ${\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}}$-полный .${\displaystyle \Пи _{1}}$
• ${\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{конечен}}\}}$-полный .${\displaystyle \Сигма _{2}}$
• ${\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ бесконечно}}\}}$-полный .${\displaystyle \Пи _{2}}$
• ${\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}}$-полный .${\displaystyle \Пи _{2}}$
• ${\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ является полным и постоянным}}\}}$-полный .${\displaystyle \Пи _{2}}$
• ${\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ кофинитен}}\}}$-полный .${\displaystyle \Сигма _{3}}$
• ${\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ вычислимо}}\}}$-полный .${\displaystyle \Сигма _{3}}$
• ${\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ расширяется до полной вычислимой функции}}\}}$-полный .${\displaystyle \Сигма _{3}}$
• ${\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e} \equiv _ {\mathrm {T} }\mathrm {HP} \}}$является -полным, где находится проблема остановки .${\displaystyle \Сигма _{4}}$${\displaystyle \mathrm {HP} }$

Эмпирически, если «наиболее очевидным» определением множества является [соответственно ], мы обычно можем показать, что оно является -полным [соответственно -полным].${\displaystyle А}$${\displaystyle \Сигма _{n}}$${\displaystyle \Пи _{n}}$${\displaystyle А}$${\displaystyle \Сигма _{n}}$${\displaystyle \Пи _{n}}$

• Одифредди, ПГ (1992). Классическая теория рекурсии, том 1. Elsevier. стр. 668. ISBN 0-444-89483-7.
• Роджерс-младший, Хартли (1987). Теория рекурсивных функций и эффективная вычислимость . MIT Press. стр. 482. ISBN 0-262-68052-1.