Классы частично рекурсивных функций, в частности, они дают все индексы функций в этом классе в соответствии с фиксированным перечислением частично рекурсивных функций.
В теории вычислимости , множество индексов описывают классы вычислимых функций ; в частности, они дают все индексы функций в определенном классе в соответствии с фиксированной гёделевской нумерацией частично вычислимых функций.
Определение [ править ] Позвольте быть вычислимым перечислением всех частично вычислимых функций и быть вычислимым перечислением всех перечислимых множеств . φ е {\ displaystyle \ varphi _ {e}} W е {\ displaystyle W_ {e}}
Позвольте быть класс частично вычислимых функций. Если то есть множество индексов из . В общем случае это набор индексов, если для каждого с (т.е. они индексируют одну и ту же функцию) у нас есть . Интуитивно это наборы натуральных чисел, которые мы описываем только со ссылкой на функции, которые они индексируют. А {\ displaystyle {\ mathcal {A}}} А знак равно { Икс : φ Икс ∈ А } {\ displaystyle A = \ {x: \ varphi _ {x} \ in {\ mathcal {A}} \}} А {\ displaystyle A} А {\ displaystyle {\ mathcal {A}}} А {\ displaystyle A} Икс , y ∈ N {\ displaystyle x, y \ in \ mathbb {N}} φ Икс ≃ φ y {\ displaystyle \ varphi _ {x} \ simeq \ varphi _ {y}} Икс ∈ А ↔ y ∈ А {\ displaystyle x \ in A \ leftrightarrow y \ in A}
Индексные множества и теорема Райса [ править ] Большинство наборов индексов невычислимы, за исключением двух тривиальных исключений. Об этом говорится в теореме Райса :
Позвольте быть класс частично вычислимых функций с его набором индексов . Then вычислимо тогда и только тогда, когда оно пустое или целиком . C {\ displaystyle {\ mathcal {C}}} C {\displaystyle C} C {\displaystyle C} C {\displaystyle C} C {\displaystyle C} N {\displaystyle \mathbb {N} }
Теорема Райса гласит, что «любое нетривиальное свойство частично вычислимых функций неразрешимо». [1]
Полнота арифметической иерархии [ править ] Наборы индексов предоставляют множество примеров наборов, завершенных на каком-то уровне арифметической иерархии . Здесь мы говорим, что набор является -полным, если для каждого набора существует m-сокращение от до . -полнота определяется аналогично. Вот несколько примеров: [2] Σ n {\displaystyle \Sigma _{n}} A {\displaystyle A} Σ n {\displaystyle \Sigma _{n}} Σ n {\displaystyle \Sigma _{n}} B {\displaystyle B} B {\displaystyle B} A {\displaystyle A} Π n {\displaystyle \Pi _{n}}
E m p = { e : W e = ∅ } {\displaystyle \mathrm {Emp} =\{e:W_{e}=\varnothing \}} Π 1 {\displaystyle \Pi _{1}} F i n = { e : W e is finite } {\displaystyle \mathrm {Fin} =\{e:W_{e}{\text{ is finite}}\}} Σ 2 {\displaystyle \Sigma _{2}} I n f = { e : W e is infinite } {\displaystyle \mathrm {Inf} =\{e:W_{e}{\text{ is infinite}}\}} Π 2 {\displaystyle \Pi _{2}} T o t = { e : φ e is total } = { e : W e = N } {\displaystyle \mathrm {Tot} =\{e:\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}} Π 2 {\displaystyle \Pi _{2}} C o n = { e : φ e is total and constant } {\displaystyle \mathrm {Con} =\{e:\varphi _{e}{\text{ is total and constant}}\}} Π 2 {\displaystyle \Pi _{2}} C o f = { e : W e is cofinite } {\displaystyle \mathrm {Cof} =\{e:W_{e}{\text{ is cofinite}}\}} Σ 3 {\displaystyle \Sigma _{3}} R e c = { e : W e is computable } {\displaystyle \mathrm {Rec} =\{e:W_{e}{\text{ is computable}}\}} Σ 3 {\displaystyle \Sigma _{3}} E x t = { e : φ e is extendible to a total computable function } {\displaystyle \mathrm {Ext} =\{e:\varphi _{e}{\text{ is extendible to a total computable function}}\}} Σ 3 {\displaystyle \Sigma _{3}} C p l = { e : W e ≡ T H P } {\displaystyle \mathrm {Cpl} =\{e:W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}} проблема остановки . Σ 4 {\displaystyle \Sigma _{4}} H P {\displaystyle \mathrm {HP} } Эмпирически, если «наиболее очевидным» определением множества является [соотв. ], мы обычно можем показать, что является -полным [соотв. -полный]. A {\displaystyle A} Σ n {\displaystyle \Sigma _{n}} Π n {\displaystyle \Pi _{n}} A {\displaystyle A} Σ n {\displaystyle \Sigma _{n}} Π n {\displaystyle \Pi _{n}}
^ Odifreddi, П. Классическая теория рекурсии, Том 1 . ^ Соаре, Роберт I. (2016), "Сводимость по Тьюрингу" , Вычислимость по Тьюрингу , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 51–78, ISBN 978-3-642-31932-7 , получено 2021-04-21 Одифредди, PG (1992). Классическая теория рекурсии, Том 1 . Эльзевир. п. 668. ISBN 0-444-89483-7 Роджерс-младший, Хартли (1987). Теория рекурсивных функций и эффективной вычислимости . MIT Press. п. 482. ISBN. 0-262-68052-1 
