<p>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.</p>

<p><i>Additional Details:</i> 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.</p>

CC BY-SA 3.0
2017-10-30T03:43:14.047Z
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}$?
Michael
CC BY-SA 3.0
2017-10-30T06:19:12.330Z
@Michael I added additional details to the answer.
Dmytro Taranovsky
CC BY-SA 3.0
2017-10-28T17:30:46.793Z
2017-10-30T06:18:05.860Z
2017-10-30T06:18:05.860Z
Dmytro Taranovsky
<p>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.</p>

CC BY-SA 3.0
2017-10-28T02:50:16.227Z
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
user1952009
CC BY-SA 3.0
2017-10-30T03:44:36.930Z
Thank you. But how to related the query output (halt or not halt) with the accept or reject?
Michael
<oracles><pspace>
How to prove $P^{Halt} = PSPACE^{Halt}$
Michael
# How to prove $P^{Halt} = PSPACE^{Halt}$

(Asked by: username_0 on 2017-10-28)

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.

**Tags:** oracles, pspace

> **Comments:**
> **username_1**: 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  
> **username_0**: Thank you. But how to related the query output (halt or not halt) with the accept or reject?  

---

## 1 answers

### Answer by username_2 on 2017-10-28. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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}$?  
> **username_2**: @username_0 I added additional details to the answer.  

---

