In other words, if you aren’t trying to work with a specific machine (such as the one in the Wolfram Prize), then you can arrange for the machine itself to do all the required tape initialisation “from scratch”. Of course that means that machine is only good for one thing – because we’ve effectively “hardcoded” everything.

Hopefully this helps make it clear that just being able to start with a “blank” background or repetitive pattern on your tape, doesn’t give your machine any more “power” at all in terms of what it can ultimately do.

However, if you’re forced to work with a particular machine and/or limited numbers of states/symbols/rules, then having the tape initialised for you in some particular way might just be enough to allow things to work.

Of course, you’re implicity assuming BPP != PSPACE when you say that’s a counterexample…;)

Alas, I don’t know the right “metric over complexity classes” to answer that question. (Another issue is that the power of the prover in interactive protocols has been understudied. People do comment on what prover power suffices for a given protocol; what they haven’t done as much is to start with the prover’s complexity and then ask what it can prove.)

I assume, by the way, that we have to ensure by physical means that the machines are “prohibited from talking to each other”? There’s no purely mathematical way to detect or guard against conspiracy between the provers, right?

Yes, that’s exactly right. In fact, a beautiful recent series of papers has studied what happens if the provers don’t communicate, but do share quantum entanglement. (Short answer: it seems that some protocols break and others don’t.)

On your point (2): is that kind of result something you’d expect to hold for most classes of prover? That is, are multiple isolated provers of class X generally more powerful than a single one (except in the trivial case where the prover is no more powerful than the verifier)? If so, would it be more relevant to ask whether MIP_BQP=BQP (and more generally, “For which X is MIP_X=X?”)? I assume Wolfram would be convinced just as well by a demonstration that needed two or more quantum computers!

I assume, by the way, that we have to ensure by physical means that the machines are “prohibited from talking to each other”? There’s no purely mathematical way to detect or guard against conspiracy between the provers, right?

Finally, on the X->Y->Z question: nice counterexample! I’d been hoping there might be scope for a kind of “middleman” scenarios, in which X can’t convince Z of something, but it can convince Y, who in turn can convince Z. But now I see that whatever the relative powers of X, Y and Z, at least one of X and Y will be redundant.

Is this general question — “For which X is IP_X=X” — one that has been extensively studied already? Is there a name for classes that meet that criterion?

Not that I know of.

Thinking about it further, it seems that there’s a sense in which these classes are the only “useful” ones to us.

When I try that view on for size, two caveats immediately spring to mind:

(1) It could be that the weakest prover convincing us about X belongs to a larger class Y, in which case we have to worry about both classes. (I.e. if you want to be convinced about X problems, a Y machine is what you have to buy.)

(2) You can also consider multiple and competing provers. For example, there’s a theorem that if you can communicate with two EXP machines — one trying to convince you that some EXP machine M accepts, the other trying to convince you that M rejects — you can play them against each other and figure out the truth in polynomial time. It’s also known that, if you can interrogate two cooperating provers who are prohibited from talking to each other, then you can verify any problem in NEXP. (For this theorem, the provers themselves need to be more powerful than NEXP — I think Σ₂EXP.) So, should we allow these things?

if X can convince Y, and Y can convince Z, does that mean that X can convince Z?

Another great question!

If you assume Y⊆X, then the answer is yes — for then the X machine can just simulate the interaction between Y and Z that causes Z to accept.

On the other hand, if you don’t assume Y⊆X, then I can give you a counterexample. A BPP machine can convince a PSPACE machine of anything in PSPACE (by doing absolutely nothing); a PSPACE machine can convince a BPP machine of anything in PSPACE (by the IP=PSPACE Theorem); but combining these, it doesn’t follow that BPP machine can convince a BPP machine of anything in PSPACE!

Thinking about it further, it seems that there’s a sense in which these classes are the only “useful” ones to us. By that, I mean that if you had a super-powerful computer that could solve problems vastly beyond your own abilities, but which couldn’t reliably convince you that it had got the right answer, then it wouldn’t do you much good to consult it. You may as well ask a Magic 8-Ball. Viewed in that way, your question about BQP is worth a lot more than $25!

We’ve been assuming that the verifier is BPP, but I guess we can get some interesting questions by allowing that to vary as well. If we let IP(X,Y) be the class of problems that have an interactive proof with prover of class X and verifier of class Y, then what we’ve called IP_X above becomes IP(X,BPP). It’s still the case that IP(X,Y) ⊆ X for all Y, and IP(X,Y)=Y for all X equal or weaker than Y. With this extra degree of freedom, we can pose questions like: is it the case that IP(X,Y) ∩ IP(Y,Z) ⊆ IP(X,Z)? That is, if X can convince Y, and Y can convince Z, does that mean that X can convince Z? [Again, maybe the answer to that is obvious, but it's not clear to me right now].

The second statement is not a statement of the principle itself, but rather specific implications. I hope you are just being sloppy rather than intentionally mean-spirited, since you obviously have an anti-wolfram agenda, but the Church-Turing thesis clearly does not say anything at all about the distribution of universality, or the relationship of universality to complex behavior, which is certainly the point of the second statement you quote. I recommend actually understanding NKS before accusing people of plagiarism.

To understand the relationship of the PCE to the Church-Turing thesis, it is important to note that the PCE is not a statement about systems themselves, but rather a statement about specific computations performed by systems. The PCE does make a prediction about the distribution of universality, but that is ultimately a derivative statement that does not capture the full principle.

Finally, there is a conceptually straightforward way to quantify “almost”, at least for abstract computational systems. One just enumerates simple programs in a variety of frameworks, and attempts to answer the question in its various cases. If say 95% of simple programs that exhibit complexity end up universal, most reasonable people would agree that means “almost all” . (To actually do this would require a signficant research program, complete with automated theorem proving to deal with all the different cases… but that is what NKS advocates be done). If one gets to 45% and then finds certain classes that don’t seem to be provably universal, then one becomes suspicious.

(of course there then remains the question of how the distributions of behavior of simple program relates to more complicated ones, and to systems in nature)