Low basis theorem (original) (raw)
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 .
| Property | Value |
|---|---|
| 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 | https://books.google.com/books%3Fid=KqeXZ4pPd5QC&pg=PA54 https://archive.org/details/handbookofcomput0140unse/page/37 |
| dbo:wikiPageID | 9767227 (xsd:integer) |
| dbo:wikiPageLength | 4240 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120062686 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Arithmetical_hierarchy dbr:Basis_theorem_(computability) dbr:Halting_problem dbc:Computability_theory dbr:Turing_jump dbr:Low_(computability) dbr:PA_degree dbr:Π01_class dbr:Springer-Verlag |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Mathlogic-stub |
| dcterms:subject | dbc:Computability_theory |
| 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 | freebase:Low basis theorem wikidata:Low basis theorem dbpedia-ja:Low basis theorem dbpedia-zh:Low basis theorem https://global.dbpedia.org/id/4r2cN |
| prov:wasDerivedFrom | wikipedia-en:Low_basis_theorem?oldid=1120062686&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Low_basis_theorem |
| is dbo:wikiPageDisambiguates of | dbr:Basis_theorem |
| is dbo:wikiPageRedirects of | dbr:Low_Basis_Theorem |
| is dbo:wikiPageWikiLink of | dbr:Carl_Jockusch dbr:List_of_Vanderbilt_University_people dbr:List_of_forcing_notions dbr:Reverse_mathematics dbr:Kőnig's_lemma dbr:Low_Basis_Theorem dbr:Basis_theorem_(computability) dbr:Basis_theorem dbr:Low_(computability) dbr:Robert_I._Soare dbr:PA_degree dbr:Slicing_the_Truth |
| is foaf:primaryTopic of | wikipedia-en:Low_basis_theorem |