Английская Википедия:Computable isomorphism

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

In computability theory two sets <math>A, B</math> of natural numbers are computably isomorphic or recursively isomorphic if there exists a total computable and bijective function <math>f \colon \N \to \N</math> such that the image of <math>f</math> restricted to <math>A\subseteq \N</math> equals <math>B\subseteq \N</math>, i.e. <math>f(A) = B</math>.

Further, two numberings <math>\nu</math> and <math>\mu</math> are called computably isomorphic if there exists a computable bijection <math>f</math> so that <math>\nu = \mu \circ f</math>. Computably isomorphic numberings induce the same notion of computability on a set.

Theorems

By the Myhill isomorphism theorem, the relation of computable isomorphism coincides with the relation of mutual one-one reducibility.

References

• Шаблон:Citation.

Шаблон:Comp-sci-theory-stub Шаблон:Mathlogic-stub