I came across this paper by Scott Aaronson and though I understand nothing of quantum computing, the fact that there was an (even hypothetical and probably unrealizable) model of ALL which he claims, theoretical or otherwise, that solves ALL.
Because ALL is apparently defined as the class (aptly) of all decision problems, this seems to completely transcend all Turing degrees and the arithmetical hierarchy, which blows my mind because this is the first I've heard of any approach, hypercomputation or otherwise, that does that.
So my question is two-fold:
- Does solving
ALLreally do what I what I just laid out above, in particular does it transcend all oracles? - Does the approach laid out in the paper do that?
Yes, your understanding is correct. Note that the "programs" allowed in this paper cannot be described using a finite amount of information, since they include an infinite sequence of "quantum advice states" (one for each possible length of input). Note that if you allow such extra information with no bound on its length, it is trivial that you can compute any language: just let your advice state for inputs of length $n$ encode what all of the outputs should be on inputs of length $n$. In this case the result is more surprising since the size of the advice state is limited to being polynomial in $n$, but it is still not too shocking.