В теории вычислимости , множество индексов описывают классы вычислимых функций ; в частности, они дают все индексы функций в определенном классе в соответствии с фиксированной гёделевской нумерацией частично вычислимых функций.
Определение
Позволять вычислимое перечисление всех частично вычислимых функций, и вычислимое перечисление всех перечислимых множеств .
Позволять - класс частично вычислимых функций. Если тогда является множество индексов из. В общем является индексным набором, если для каждого с участием (т.е. они индексируют одну и ту же функцию), мы имеем . Интуитивно это наборы натуральных чисел, которые мы описываем только со ссылкой на функции, которые они индексируют.
Индексные множества и теорема Райса
Большинство наборов индексов невычислимы, за исключением двух тривиальных исключений. Об этом говорится в теореме Райса :
Позволять - класс частично вычислимых функций с индексным множеством . потом вычислимо тогда и только тогда, когда пусто, или все из .
Теорема Райса гласит, что «любое нетривиальное свойство частично вычислимых функций неразрешимо». [1]
Полнота арифметической иерархии
Наборы индексов предоставляют множество примеров наборов, завершенных на каком-то уровне арифметической иерархии . Здесь мы говорим набор является -полное, если для каждого набор , есть m-редукция от к . -полнота определяется аналогично. Вот несколько примеров: [2]
- является -полный.
- является -полный.
- является -полный.
- является -полный.
- является -полный.
- является -полный.
- является -полный.
- является -полный.
- является -полный, где это проблема остановки .
Эмпирически, если "наиболее очевидное" определение множества является [соотв. ], обычно можно показать, что является -полный [соотв. -полный].
Заметки
- ^ Odifreddi, П. Классическая теория рекурсии, Том 1 .; стр. 151
- ^ Соаре, Роберт И. (2016), «Сводимость по Тьюрингу» , Вычислимость по Тьюрингу , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 51–78, ISBN 978-3-642-31932-7, получено 2021-04-21