About: Computable isomorphism

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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, the relation of computable isomorphism coincides with the relation of mutual one-one reducibility. 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.

Property Value
dbo:abstract
  • Rekursive Isomorphie ist in der Berechenbarkeitstheorie eine Äquivalenzrelation auf Mengen natürlicher Zahlen. (de)
  • 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, the relation of computable isomorphism coincides with the relation of mutual one-one reducibility. 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. (en)
dbo:wikiPageID
  • 2611685 (xsd:integer)
dbo:wikiPageLength
  • 1449 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1028777541 (xsd:integer)
dbo:wikiPageWikiLink
dbp:date
  • June 2021 (en)
dbp:reason
  • f is a function on naturals, not on sets of naturals, so what is f? (en)
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • Rekursive Isomorphie ist in der Berechenbarkeitstheorie eine Äquivalenzrelation auf Mengen natürlicher Zahlen. (de)
  • 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, the relation of computable isomorphism coincides with the relation of mutual one-one reducibility. 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. (en)
rdfs:label
  • Rekursive Isomorphie (de)
  • Computable isomorphism (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License