Back to Search Start Over

Pseudojump Operators and $\Pi^0_1$ Classes.

Authors :
Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Nierstrasz, Oscar
Rangan, C. Pandu
Steffen, Bernhard
Sudan, Madhu
Terzopoulos, Demetri
Tygar, Doug
Vardi, Moshe Y.
Weikum, Gerhard
Cooper, S. Barry
Löwe, Benedikt
Sorbi, Andrea
Cenzer, Douglas
LaForte, Geoffrey
Source :
Computation & Logic in the Real World; 2007, p146-151, 6p
Publication Year :
2007

Abstract

For a pseudojump operator VX and a $\Pi^0_1$ class P, we consider properties of the set {VX: X ∈ P}. We show that there always exists X ∈ P with $V^X \leq_T {\mathbf 0'}$ and that if P is Medvedev complete, then there exists X ∈ P with $ V^X \equiv_T {\mathbf 0'}$. We examine the consequences when VX is Turing incomparable with VY for X ≠ Y in P and when $W_e^X = W_e^Y$ for all X,Y ∈ P. Finally, we give a characterization of the jump in terms of $\Pi^0_1$ classes. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISBNs :
9783540730002
Database :
Supplemental Index
Journal :
Computation & Logic in the Real World
Publication Type :
Book
Accession number :
33191441
Full Text :
https://doi.org/10.1007/978-3-540-73001-9_15