What Amazon is describing is something entirely different. They aren't just compressing the content, they actually render of the page remotely through their EC2 service. The bottleneck for web browsing on small devices like phones/tablets is often in the render time instead of the transfer time. Assuming you have a decent wireless connection, this should do a lot more to improve your web browsing experience than just content compression would.

This isn't really right. humans are capable of recognizing when SOME algorithms will halt. That isn't very spectacular, computers can do the same. Solving the halting problem would mean being able to recognize whether ANY algorithm will halt without resorting to dumb brute force methods. Humans are limited just as much as computers in this respect.

If the opt-in notices get annoying, browsers could detect the requests and opt you in automatically. Problem solved.