HOME

TheInfoList



Click Here for Items Related To - Computable Isomorphism
OR:
Computable Isomorphism on:   [Wikipedia]   [Google]   [Amazon]

In
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ...
two sets A;B \subseteq \N of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s are computably isomorphic or recursively isomorphic if there exists a
total Total may refer to: Mathematics * Total, the summation of a set of numbers * Total order, a partial order without incomparable pairs * Total relation, which may also mean ** connected relation (a binary relation in which any two elements are compa ...
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...
f \colon \N \to \N with f(A) = B. By the Myhill isomorphism theorem,Theorem 7.VI, Hartley Rogers, Jr., ''Theory of recursive functions and effective computability'' the relation of computable isomorphism coincides with the relation of mutual one-one reducibility. Two
numbering There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be considered to be examples of a primary key of a database management s ...
s \nu and \mu are called computably isomorphic if there exists a computable bijection f so that \nu = \mu \circ f Computably isomorphic numberings induce the same notion of computability on a set.


References

*. Reduction (complexity) {{mathlogic-stub