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.

| cite | improve this question | | | | |
  • $\begingroup$ 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 $\endgroup$ – user1952009 Oct 28 '17 at 2:50
  • $\begingroup$ Thank you. But how to related the query output (halt or not halt) with the accept or reject? $\endgroup$ – Michael Oct 30 '17 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.

| cite | improve this answer | | | | |
  • $\begingroup$ 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}$? $\endgroup$ – Michael Oct 30 '17 at 3:43
  • $\begingroup$ @Michael I added additional details to the answer. $\endgroup$ – Dmytro Taranovsky Oct 30 '17 at 6:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.