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


Relativized Schnorr tests with universal behavior
Authors:Nicholas Rupprecht
Affiliation:1. Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109, USA
Abstract:A Schnorr test relative to some oracle A may informally be called “universal” if it covers all Schnorr tests. Since no true universal Schnorr test exists, such an A cannot be computable. We prove that the sets with this property are exactly those with high Turing degree. Our method is closely related to the proof of Terwijn and Zambella’s characterization of the oracles which are low for Schnorr tests. We also consider the oracles which compute relativized Schnorr tests with the weaker property of covering all computable reals. The degrees of these oracles strictly include the hyperimmune degrees and are strictly included in the degrees not computably traceable.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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