| 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 |
dbr:Myhill_isomorphism_theorem dbc:Reduction_(complexity) dbr:Numbering_(computability_theory) dbr:Computability_theory_(computer_science) dbr:Computable_function dbr:Bijective dbr:Many-one_reduction dbr:Total_function dbr:Natural_number |
| 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 |
dbt:Citation dbt:Explain dbt:Reflist dbt:Mathlogic-stub dbt:Comp-sci-theory-stub |
| dct:subject |
dbc:Reduction_(complexity) |
| 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 |
freebase:Computable isomorphism wikidata:Computable isomorphism dbpedia-de:Computable isomorphism https://global.dbpedia.org/id/4hjAH |
| prov:wasDerivedFrom |
wikipedia-en:Computable_isomorphism?oldid=1028777541&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Computable_isomorphism |
| is dbo:wikiPageRedirects of |
dbr:Computably_isomorphic |
| is dbo:wikiPageWikiLink of |
dbr:Myhill_isomorphism_theorem dbr:Creative_and_productive_sets dbr:Computably_isomorphic |
| is foaf:primaryTopic of |
wikipedia-en:Computable_isomorphism |