Please read the section in the diagonalization chapter on oracle machines, and the Baker-Gill-Solovay result.

Advertisements