2
$\begingroup$

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?

  • 1
    (If you don’t use the ping feature, I probably won’t see your responses.) All right; now I see what you’re getting at. @Srivatsan’s question is then why you think that we can prove that a specific Turing machine performs a specific task. For a sufficiently simple task we probably can; I don’t know whether this one qualifies, though I’d not be surprised. The answer to your *Are you telling me* question, however, is that in general I would **not** expect to be able to deduce what it does.2011-11-05

0 Answers 0