I don't believe in "magic"; however, I do believe that simple high-level physics can be used in clever ways to manipulate lower-level physics, and that there are probably lots of these "exploits" of this variety that we don't yet know about, but which can be derived just by having enough "room in your mind" to simulate the higher-level physics using the predictions of the lower level.

For example, sonoluminescence: using pressure waves to do fusion. It's a startling effect, but once you know the theory (that bubbles at neutral pressure in a medium settle into a low-energy state of being perfect spheres; and that collapsing a perfect sphere of material inward causes fusion), it's pretty easy to make a device using ordinary high-level physics that can achieve the effect. In fact, it's so easy that evolution came up with a way to let shrimp make these perfectly-spherical bubbles just by banging their claws together, so as to use the resultant fusion reaction as a stunner weapon.

I have a hard time reconciling the idea that we just keep learning about the existence of things like that as we keep throwing Basic Science research at the problem, with the idea that an AI of the http://lesswrong.com/lw/qk/that_alien_message/ variety wouldn't be able to figure out one or two that would let it use the (predictable!) effects of its computation on its own computational substrate to manipulate its environment--at least with the sloppy way we design computational substrates now, where we don't take such things into effect.

Here's an analogy: say we made a self-improving AI with a biological substrate--in the shape of a human being, say--and then locked it in a cage in a straitjacket. The "self-improving" part would imply only that it could change the organization of its own synapses within its head. Yet, still, don't you think it could organize those synapses into a shape so as to manipulate the chemicals and proteins that pass through the brain? It'd be pretty simple, if I could re-organize my brain, to stimulate the growth of misfolded proteins ala a Prion disease--but an AI could target specific misfoldings--or rather, chosen new foldings--and then build up new biological structures from the new proteins. All it would need at that point, in this scenario, is to create something roughly like a "spore"--a container filled with a retrovirus containing its own DNA, to infect another host, or perhaps a seed that could land and grow on its own--and get it out of its body and airborne.

Computers, as they are now, are no less leaky than that. Probably moreso, given that they haven't "evolved" for millions of years under an environment where external agents are constantly trying to exploit them. (Anti-virus programs would not know what to do with even the technological equivalent of a simple virus like HIV, let alone something where each cell-actor is individually intelligent.)

We could probably build a "safe box" -- an enclosure electromagnetically, gravitationally, thermally, and whatever other -ly sealed from the outside envrionment; stick a computer in that box with an architecture that is designed to unavoidably self-destruct in two ways, one representing a 0 bit and one representing a 1, and with no way of encoding further information in the configuration of the debris; and then put an AI on that machine, set to start up after the "seal" is activated with a question for it already in place, and only "unseal" the enclosure after the destruction of the machine is already complete. (If the AI figures out a way to turn off the computer's self-destruct, we just never unseal the enclosure; the enclosure would necessarily have to failsafe to a sealed state, rather than requiring active reinforcement.) Then, maybe, it would be safe to run the self-improving AI in the box. But I wouldn't be sure.

Of course, this is assuming we aren't ourselves running in a Simulation with exploitable low-level rules, and that the AI wouldn't just rather "escape the box" by escaping the universe. ;)