It is well known that being able to compute Busy Beaver numbers would allow one to solve (in theory) such open problems as Goldbach's conjecture. Simply run a Turing machine with $n$ states to check search for counterexamples, and either wait for it to terminate or see if the number of shifts exceeds the $n$th Busy Beaver number.
Obviously such a problem is not computationally feasible, since the 6th Busy Beaver number already exceeds (by a ridiculous amount) our computational capacity to perform such a search, and a useful Turing machine would likely need more than 6 states.
But out of curiosity, is the minimal number of states required to perform such an unbounded search for a Goldbach counterexample known? What about for simpler problems?
This seems to be related to Kolmogorov complexity (which is not computable), but I don't know much about that. Couldn't one in principle just search through all Turing machines with a given number of states until one finds a machine which acts as desired?