X86 address translation is turing complete
Was following references around some papers on weird attack techniques like ROP, and ran across this talk
Basically... you can implement a TM using the x86's MMU (or x64, apparently), without it ever loading an instruction to actually execute through the pipeline by abusing edge cases and processor weirdities.
The talk is long (1hr), but if you're familiar with how PaX emulated NX bits before there was hardware support (or really even if not) you can probably skip from about 3:00 in to 13:30, and then skip 17:00 to 37:50. Then set the playback speed to 1.5x.
My memory's fuzzy but I'm pretty sure Raymond Chen wrote an article about this a few years ago...