Here's one intuitive way to think about what this means: Imagine that you stumble on two infinitely powerful computers that share a bunch of entangled quantum

Here's one intuitive way to think about what this means: Imagine that you stumble on two infinitely powerful computers that share a bunch of entangled quantum state. Further, let's say you know how to write software for them but you need a way to check that the answers are correct. And you want to know with near certainty that your programs ran correctly, even if one of the infinitely powerful computers is evil and will use its entire intellect to convince you of something that's untrue. Aside: this means that cryptography doesn't work---you can't use the discrete log assumption to solve this problem, you can't use collision resistant hashing, etc. Ok, so this paper shows that, if you can figure out how to program those computers to solve the halting problem, you can then create an error detection protocol (see below) that you can check on a laptop computer and that almost perfectly (like, except with exponentially small probability) detects errors in your halting detector's execution. You can use your laptop to ensure that your infinitely powerful, possibly evil lunatic twin Hal2^9000s aren't lying to you. Or, as BFLS91 says, "controlling a herd of supercomputers from [your iPad]" ;) (Your error detecting protocol checker must be verified, but it's not too complicated an algorithm and we basically know how to write certified computer software for our laptops.) (Oh, and also note that you need a perfect random number generator, and your laptop has to communicate with the supercomputers while they're executing.) [edit for slightly more precision]