Теорема Райса – Шапиро - Rice–Shapiro theorem

В теория вычислимости, то Теорема Райса – Шапиро является обобщением Теорема Райса, и назван в честь Генри Гордон Райс и Норман Шапиро.^[1]

Официальное заявление

Позволять А быть набором частично рекурсивных унарных функции в области натуральные числа так что набор ${displaystyle Ix(A):={nmid varphi _{n}in A}}$ является рекурсивно перечислимый, куда ${displaystyle varphi _{n}}$ обозначает ${displaystyle n}$-я частично рекурсивная функция в Гёделевская нумерация.

Тогда для любой унарной частично рекурсивной функции ${displaystyle psi }$, у нас есть:

${displaystyle psi in ALeftrightarrow exists }$ конечная функция ${displaystyle heta subseteq psi }$ такой, что ${displaystyle heta in A.}$

В данном утверждении конечная функция - это функция с конечной областью определения ${displaystyle x_{1},x_{2},...,x_{m}}$ и ${displaystyle heta subseteq psi }$ означает, что для каждого ${displaystyle xin {x_{1},x_{2},...,x_{m}}}$ он считает, что ${displaystyle psi (x)}$ определено и равно ${displaystyle heta (x)}$.

С точки зрения эффективной топологии

Для любой конечной унарной функции ${displaystyle heta }$ на целых числах, пусть ${displaystyle C( heta )}$ обозначают `` пирамиду '' всех частично рекурсивных функций, которые определены, и согласуются с ${displaystyle heta }$,на ${displaystyle heta }$домен.

Оборудуйте набор всех частично рекурсивных функций с топологией, сгенерированной thesefrusta как основание. Обратите внимание, что для каждого усеченного конуса ${displaystyle C}$, ${displaystyle Ix(C)}$ рекурсивно перечислимо. В целом это справедливо для каждого набора ${displaystyle A}$частично рекурсивных функций:

${displaystyle Ix(A)}$ рекурсивно перечислим, если и только если ${displaystyle A}$ рекурсивно перечислимое объединение фрусты.

Примечания

1. Роджерс-младший, Хартли (1987). Теория рекурсивных функций и эффективной вычислимости. MIT Press. ISBN  0-262-68052-1.

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

• Катленд, Найджел (1980). Вычислимость: введение в теорию рекурсивных функций. Издательство Кембриджского университета.; Теорема 7-2.16.
• Роджерс-младший, Хартли (1987). Теория рекурсивных функций и эффективной вычислимости. MIT Press. п. 482. ISBN  0-262-68052-1.
• Одифредди, Пьерджоржио (1989). Классическая теория рекурсии. Северная Голландия.