Low 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 .
Wikipage disambiguates
Wikipage redirect
primaryTopic
Low 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 .
has abstract
The low basis theorem is one o ...... alent to the halting problem .
@en
低基定理是关于不可解度的定理。
@zh
計算可能性理論における低基底定理（英: low basis ...... の計算可能な無限二分木は低い無限枝を持つ」ことを述べている。
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,000,171,651
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
comment
The low basis theorem is one o ...... alent to the halting problem .
@en
低基定理是关于不可解度的定理。
@zh
計算可能性理論における低基底定理（英: low basis ...... の計算可能な無限二分木は低い無限枝を持つ」ことを述べている。
@ja
label
Low basis theorem
@en
低基定理
@zh
低基底定理
@ja