WikiDer > Теорема Райса – Шапиро

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

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

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

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

${displaystyle psi в ALeftrightarrow существует}$ конечная функция ${displaystyle heta substeq psi}$ такой, что ${displaystyle heta на языке A.}$

В данном утверждении конечная функция - это функция с конечной областью определения ${displaystyle x_ {1}, x_ {2}, ..., x_ {m}}$ и ${displaystyle heta substeq 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}$ рекурсивно перечислимое объединение фрусты.

Примечания

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

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

Эта статья о вычислительной технике заглушка. Вы можете помочь Википедии расширяя это. v т е