well humans can certainly deal with a lot of halting problems, because humans can make decisions that aren't obviously computational or algorithmic in nature.

Which is actually the relevant question that people seem to have skipped over completely, at least from living organisms it appears fairly likely that intelligence isn't just computational, or at least not simply computational in the way turing machines are.