Complexity class with arithmetical oracle. Although I feel the answer to the following question is negative, I can't get any precise results neither find anything to read. The question is: Would a complete oracle from some level of arithmetical hierarchy anyhow boost the complexity classes, in terms of complexity? For example, would a **P** machine with halting problem oracle be able to solve anything from **EXPTIME**? Or **LOGSPACE** machine with the same oracle to solve something from **PSPACE**? Thank you.

Yes ofcourse,

With a halting oracle you can solve any decidable problem in polynomial time as follows:

Let L be a decidable language, and let M its decider.

K: on input x do{

Construct a turing machine N: on input y {


If M(y) = true
then output true
else while(1)


}

query the HALT oracle with (N,x) and output its result

}

Clearly $K(x) = true \iff M(x) = true$. It also solves this problem in polynomial time. Also, the machine N does not depend on the input, so this problem only needs a constant amount of space. So we can solve any decidable problem, even in logspace, with a halting oracle.