| dbo: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)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4240 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| 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)
|
| rdfs:label
|
- Low basis theorem (en)
- 低基底定理 (ja)
- 低基定理 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
