The computer analogy is definitely off. For one thing, rationality is kind of bolted on to our linguistic ability. It's not deeply seated in our brain; it takes substantial energy to engage in logical reasoning and we're not that great at it; even very skilled mathematicians make trivial mistakes.
Deeper in our brain is reasoning about causality. But even that is more of an input to our reactions and emotions than it is as a consciously accessible function, and it too is often wrong.
As you said, it's a heuristic. We certainly can't solve the halting problem with brain magic.
Implementing algorithms doesn't need a computer, and it doesn't need something that's not a computer.
That said, with enough willpower why couldn't you implement a universal Turing machine in your brain? I think you would need external memory (a tape) but that's not a problem.
Deeper in our brain is reasoning about causality. But even that is more of an input to our reactions and emotions than it is as a consciously accessible function, and it too is often wrong.
As you said, it's a heuristic. We certainly can't solve the halting problem with brain magic.