# How to prove $P^{Halt} = PSPACE^{Halt}$ [closed]

Halt means the halting set. $PSPACE^{Halt}$ is the class of problems that can be solved with polynomial memory (possibly exponential time), given a halting oracle.

• I'd say if you have a program which output a string of $n$ bits, you can use dichotomy to know the output after $n$ calls to the halting oracle Oct 28, 2017 at 2:50
• Thank you. But how to related the query output (halt or not halt) with the accept or reject? Oct 30, 2017 at 3:44

Using $n$ calls to the halting oracle and time $O(n^2)$, you can compute the first $n$ bits of the Chaitin's constant. Using the $n$ bits of the Chaitin's constant and unbounded time, all queries to the halting oracle of length approximately $≤n$ (depending on the representation) can be eliminated. Finally, the result can be obtained in bounded time by querying the halting oracle.
Additional Details: In the relativization of $\mathrm{PSPACE}$ here, the oracle tape counts against space usage, so a $\mathrm{PSPACE}^\mathrm{Halt}$ machine can only use queries of length $n^{O(1)}$ (though the number of the queries can be exponential). The digits of the Chaitin's constant can be used to get the number of machines of length $≤n$ that halt, and by simulating all these machines until the right number halts, we can find out exactly which of the (roughly $2^n$) machines halt. The digits of the Chaitin's constant, or just the number of the halting machines, can be computed in $n^{O(1)}$ queries by bisection.
• Thank you. However, for ${PSPACE}$, there is no upper bound for its queries. Even if $\leq n$ can be eliminated. How to compression to ${P}^{Halt}$? Oct 30, 2017 at 3:43