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 等数据库收录! |
|