Why not just pass it to an infinite number of processors and use a nondeterministic Turing machine?
But with an NDTM, even NP-complete problems can be solved within polynomial time.
"what are the odds of that?"
I'm not sure, maybe we should build an unbelievably inefficient program to calculate them.
My solution is slightly different - to avoid the Halting Problem, you can use a distributed approach. You have a very large (but finite) number of processors that you pass your programs to.