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

$\nu = \mu \circ f.\,$

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

This mathematical logic-related 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. Игры ⚽ Нужно решить контрольную? Mr Paulus Pleydell John Barber 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 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”