Computable isomorphism

In computability theory two sets A and B are computably isomorphic or recursively isomorphic if there exists a bijective computable function f with f(A) = B.
Two numberings ν and μ are called computably isomorphic if there exists a bijective computable function f so that
Computably isomorphic numberings induce the same notion of computability on a set.
This mathematical logicrelated article is a stub. You can help Wikipedia by expanding it.v · Categories:  Theory of computation
 Computability theory
 Computer science stubs
 Mathematical logic stubs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Myhill isomorphism theorem — For the Goodman–Myhill theorem in constructive set theory, see Diaconescu s theorem. In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of… … Wikipedia
List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… … Wikipedia
Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… … Wikipedia
Real number — For the real numbers used in descriptive set theory, see Baire space (set theory). For the computing datatype, see Floating point number. A symbol of the set of real numbers … Wikipedia
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia
Intuitionistic type theory — Intuitionistic type theory, or constructive type theory, or Martin Löf type theory or just Type Theory is a logical system and a set theory based on the principles of mathematical constructivism. Intuitionistic type theory was introduced by Per… … Wikipedia
Ordinal number — This article is about the mathematical concept. For number words denoting a position in a sequence ( first , second , third , etc.), see Ordinal number (linguistics). Representation of the ordinal numbers up to ωω. Each turn of the spiral… … Wikipedia
automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… … Universalium
List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic … Wikipedia
Model theory — This article is about the mathematical discipline. For the informal notion in other parts of mathematics and science, see Mathematical model. In mathematics, model theory is the study of (classes of) mathematical structures (e.g. groups, fields,… … Wikipedia
© Academic, 20002020Share the article and excerpts
We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.
Computable isomorphism

In computability theory two sets A and B are computably isomorphic or recursively isomorphic if there exists a bijective computable function f with f(A) = B.
Two numberings ν and μ are called computably isomorphic if there exists a bijective computable function f so that
Computably isomorphic numberings induce the same notion of computability on a set.
This mathematical logicrelated article is a stub. You can help Wikipedia by expanding it.