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 ex ...
two sets
of
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
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 comp ...
computable
Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is cl ...
and
bijective
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
function
such that the image of
restricted to
equals
, i.e.
.
Further, 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
In the relational model ...
s
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.
Theorems
By the
Myhill isomorphism theorem
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set. It is reminiscent of the Schröder–Bernstein theorem in set theor ...
, the relation of computable isomorphism coincides with the relation of mutual
one-one reducibility.
[Theorem 7.VI, Hartley Rogers, Jr., ''Theory of recursive functions and effective computability'']
References
*.
Reduction (complexity)
{{mathlogic-stub