About: Low basis theorem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FLow_basis_theorem

The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree , it is possible to find an infinite path through the tree with particular computability properties. The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem .

AttributesValues
rdfs:label
  • Low basis theorem (en)
  • 低基底定理 (ja)
  • 低基定理 (zh)
rdfs:comment
  • The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree , it is possible to find an infinite path through the tree with particular computability properties. The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem . (en)
  • 計算可能性理論における低基底定理（英: low basis theorem）は の任意の空でない（算術的階層を見よ）はの元を含むことを示す（Soare 1987:109）もので、1972年にとによって証明せられた（Nies 2009:57）。Cenzer (1993:53) はこれを"もしかすると クラスの理論において最も引用されている結果"と記している。 この定理の証明には クラスによる強制法が用いられている（Cooper 2004:330）。未出版の元々の証明では -構成が用いられていた（Diamondstone et al.:2010:135）。シェイファーはこの証明が実際にはの元の存在を示していることを指摘した。この意味で強化された主張は超低基底定理と呼ばれる。 クラスは木の概念と密接に関係している。クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低次数の無限枝を持つ」ことを述べている。 (ja)
  • 低基定理是关于不可解度的定理。 (zh)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree , it is possible to find an infinite path through the tree with particular computability properties. The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem . (en)
  • 計算可能性理論における低基底定理（英: low basis theorem）は の任意の空でない（算術的階層を見よ）はの元を含むことを示す（Soare 1987:109）もので、1972年にとによって証明せられた（Nies 2009:57）。Cenzer (1993:53) はこれを"もしかすると クラスの理論において最も引用されている結果"と記している。 この定理の証明には クラスによる強制法が用いられている（Cooper 2004:330）。未出版の元々の証明では -構成が用いられていた（Diamondstone et al.:2010:135）。シェイファーはこの証明が実際にはの元の存在を示していることを指摘した。この意味で強化された主張は超低基底定理と呼ばれる。 クラスは木の概念と密接に関係している。クラスに関する定理はしばしば木に関する定理として定式化される。低基底定理は「任意の計算可能な無限二分木は低次数の無限枝を持つ」ことを述べている。 (ja)
  • 低基定理是关于不可解度的定理。 (zh)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 60 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software