Вычислимый изоморфизм

В теории вычислимости два множества $A,B$ натуральных чисел вычислимо изоморфны или рекурсивно изоморфны, если существует тотально вычислимая и биективная функция $f\colon \mathbb {N} \to \mathbb {N}$ такое, что образ $f$ ограничено $A\subseteq \mathbb {N}$ равно $B\subseteq \mathbb {N}$ , то есть $f(A)=B$ .

Далее две нумерации $\nu$ и $\mu$ называются вычислимо изоморфными, если существует вычислимая биекция $f$ так что $\nu =\mu \circ f$ . Вычислимо изоморфные нумерации индуцируют то же самое понятие вычислимости на множестве.

Теоремы [ править ]

По теореме Майхилла об изоморфизме отношение вычислимого изоморфизма совпадает с отношением взаимной сводимости . ^[1]

Ссылки [ править ]

^ Теорема 7.VI, Хартли Роджерс-младший, Теория рекурсивных функций и эффективная вычислимость

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

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

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

[1] Теорема 7.VI, Хартли Роджерс-младший, Теория рекурсивных функций и эффективная вычислимость

[1]