Набор индексов (теория рекурсии) - Index set (recursion theory)

В области теория рекурсии, наборы индексов описать классы частичные рекурсивные функции, в частности, они дают все индексы функций в этом классе в соответствии с фиксированным перечислением частично рекурсивных функций (a Гёделевская нумерация ).

Определение

Исправьте перечисление всех частично рекурсивных функций или, что эквивалентно, рекурсивно перечислимый устанавливает, посредством чего еый такой набор ${displaystyle W_{e}}$ и е-я такая функция (область определения ${displaystyle W_{e}}$) является ${displaystyle phi _{e}}$.

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

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

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

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

куда ${displaystyle omega }$ это набор натуральные числа, включая нуль.

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

Примечания

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

Рекомендации

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