RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Keep that pinned in your mind.

IP: The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. There are some additional stipulations about the probability with which the verifier must accept or reject the prover’s claim.

MIP* is like IP but (a) you can have multiple provers and (b) the provers can share arbitrarily many entangled qubits.

MIP* = RE

One way to look at this is to think of MIP* as a subset of RE and then RE as a subset of MIP. RE being contained within MIP* isn’t very surprising - if it’s already in RE, then just clone a bunch of entangled copies of the “regular” Turing machine that already verifies “yes” answers in finite time and you’ve got your no-op MIP* version of the same thing. The hard part here (and where all the details that make the proof such an impressive achievement come in) is how to ensure the verifier doesn’t have to just trust the provers, for any general problem in RE, while still only running in polynomial time to achieve a certain level of probability of correctness.

MIP* \in RE is weird though.

Any decision problem where a verifier can polynomially verify a “yes” answer given info from multiple entangled provers must also be a problem where there exists a “regular” Turing machine that can verify a “yes” answer in finite time.

What’s surprising is that the “collusion” of multiple entangled provers never presents the verifier with something they can polynomially verify such that some other “regular” Turing machine couldn’t.

You don’t “get more” or “get extra” out of their being multiple provers that can “work together” in a sense. It turns out to be no different than the class of problems where a “yes” answer was already easy (finite time) to verify.

One careful point to note is that the only place in this where polynomial time comes into play is the process of the verifier validating a “yes” answer from the provers in MIP.

The process of the provers themselves may not be polynomial (though, for “yes” answers it is clear it must be finite).

RE problems are not necessarily efficiently verifiable. For example the Halting Problem itself is in RE.

The finite verifier for a “yes” answer is to run for the finite amount of time it takes to halt for that example. The MIP interactive proof could be running several of those in parallel and just ignore any entanglement and ask each one “have you halted?” They will all wait around for the finite amount of time it takes to halt and then say “yes” and the verifier can just check they all said yes (O(n) where n is number of provers). But again the trick is how to modify that algorithm so the verifier doesn’t just have to believe the provers, and the authors of the proof give that explicitly for the Halting Problem on page 154 of the paper.

Side note: it’s really hard writing prose with a term that needs an asterisk on HN - apologies for weird italics and “MIP” when it should be “MIP*”.