首页 | 本学科首页   官方微博 | 高级检索  
     


About Segment Complexity of Turing Reductions
Authors:Valeriy K. Bulitko
Abstract:We apply complexity concepts to define a new sort of sub-Turing reducibilities ≤ ?? make the degree hierarchy thinner and to obtain some new specifications of the well known jump inversion theorem of Friedberg. We show that this theorem doesn't hold when ≤ T is replaced with ≤ ??, where ?? is any countable subset of the class ?? of all total increasing functions f : ? → ?.
Keywords:Sub-Turing reducibility  Turing degree  Kolmogorov complexity  Jump inversion
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号