An Analysis In The Complexity Of ?10 Class Paths | Posted on:2019-01-15 | Degree:Master | Type:Thesis | Country:China | Candidate:Y J Cao | Full Text:PDF | GTID:2310330545485101 | Subject:Basic mathematics | Abstract/Summary: | PDF Full Text Request | Mathematical logics is an important branch of mathematics.And Recursion theory play a significant role in mathematical logics.One of its purpose is to find the true meaning of the computability and the complexity of problems.Because there are some effective ways to code the characters into nature number,we only need to focus on nature number sets which could be codified into paths of trees.Among the sets of variant Turing degrees,the computable and computably enumerable ones are undoubtedly important and fundamental.The purpose of this dissertation is to construction a computable tree including at least one path of every computably enumerable degree.But the other paths in the tree are all totally computable.Moreover,for any computably enumerable degree set,if their index set is com-putably enumerable set,we can construct a computable tree which includes at least one path of these computably enumerable degree.But the other paths in the tree are also computable. | Keywords/Search Tags: | ?10 Class, Turing Computability, Computably Enumerable, Turing Degree, Binary Tree, Modulus Function, Antibasis | PDF Full Text Request | Related items |
| |
|