A perfect implementation would be a Kolmogorov oracle. https://en.wikipedia.org/wiki/Kolmogorov_complexity#Halting_... suggests this is equivalent to a halting oracle. So, it depends what you mean by "good".