Google can and does include a Javascript interpreter in their crawler: http://www.seomoz.org/ugc/new-reality-google-follows-links-i... . They don't need to solve the halting problem in order to run a Javascript interpreter for a certain amount of time(maybe 10-15 seconds) and see how that changes the page content or redirects to a different site.

If you want to make your visitors wait until after the heat death of the universe before you actually redirect them, I'm sure you'll be able to fool Google too.