I think it's somewhere between halting and turing - given infinite resources it's likely solvable, but lacking that it's just narrowing bounds