“Low basis theorem”的意思、由来-开放百科全书

词条

Low basis theorem

释义

Statement and proof
Application
References

The low basis theorem is one of several basis theorems in computability theory, each of which shows 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 .

Statement and proof

The low basis theorem states that every nonempty class in (see arithmetical hierarchy) contains a set of low degree (Soare 1987:109). This is equivalent, by definition, to the statement that each infinite computable subtree of the binary tree has an infinite path of low degree.

The proof uses the method of forcing with classes (Cooper 2004:330). Hájek and Kučera (1989) showed that the low basis is provable in the formal system of arithmetic known as .

Application

One application of the low basis theorem is to construct completions of effective theories so that the completions have low Turing degree. For example, the low basis theorem implies the existence of PA degrees strictly below .

References

{{cite book | first=Douglas | last=Cenzer | chapterurl = https://books.google.com/books?id=KqeXZ4pPd5QC&pg=PA54 | chapter= classes in computability theory | title=Handbook of computability theory | series=Stud. Logic Found. Math. | volume=140 | publisher=North-Holland | year=1999 | pages=37–85 | mr=1720779 | zbl=0939.03047 | editor-last=Griffor | editor-first=Edward R. | isbn=0-444-89882-4 }}
{{cite book|author = Cooper, S. Barry| authorlink= S. Barry Cooper | year = 2004 | title = Computability Theory | publisher = Chapman and Hall/CRC | isbn = 1-58488-237-9}}.
{{cite journal|author1=Hájek, Petr|author2=Kučera, Antonín | year= 1989 |title = On Recursion Theory in I∑1|journal=Journal of Symbolic Logic| volume=54|number=2|pages=576–589|jstor=2274871|doi=10.2307/2274871}}
{{cite journal | first1=Carl G., Jr. | last1=Jockusch | first2=Robert I. | last2=Soare | title=Π(0, 1) Classes and Degrees of Theories | journal=Transactions of the American Mathematical Society | year=1972 | jstor=1996261 | zbl=0262.02041 | volume=173 | pages=33–56 | issn=0002-9947 | doi=10.1090/s0002-9947-1972-0316227-0}} The original publication, including additional clarifying prose.
{{cite book | last=Nies | first=André | title=Computability and randomness | series=Oxford Logic Guides | volume=51 | location=Oxford | publisher=Oxford University Press | year=2009 | isbn=978-0-19-923076-1 | zbl=1169.03034 }} Theorem 1.8.37.
{{cite book | first=Robert I. | last=Soare | title=Recursively enumerable sets and degrees. A study of computable functions and computably generated sets | series=Perspectives in Mathematical Logic | publisher=Springer-Verlag | location=Berlin | year=1987 | isbn=3-540-15299-7 | zbl=0667.03030 }}

1 : Computability theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。