“Computable isomorphism”的意思、由来-开放百科全书

词条

Computable isomorphism

释义

References

In computability theory two sets of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function with . By the Myhill isomorphism theorem,^[1] the relation of computable isomorphism coincides with the relation of one-one reduction.

Two numberings and are called computably isomorphic if there exists a computable bijection so that

Computably isomorphic numberings induce the same notion of computability on a set.

References

1. ^Theorem 7.VI, Hartley Rogers, Jr., Theory of recursive functions and effective computability

{{citation

| last = Rogers | first = Hartley, Jr. | author-link = Hartley Rogers, Jr.
| edition = 2nd
| isbn = 0-262-68052-1
| location = Cambridge, MA
| mr = 886890
| publisher = MIT Press
| title = Theory of recursive functions and effective computability
| year = 1987}}.{{DEFAULTSORT:Computable Isomorphism}}{{comp-sci-theory-stub}}{{mathlogic-stub}}

1 : Reduction (complexity)

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。