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?

$\endgroup$
  • $\begingroup$ 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? - Why are you assuming that we could, even in principle, find whether a given machine "acts as desired"? $\endgroup$ – Srivatsan Nov 4 '11 at 23:24
  • $\begingroup$ Are you telling me that if you have an explicit description of a Turing machine with two states, you can't deduce what it does? Perhaps I should qualify: two symbols allowed on the tape... $\endgroup$ – JeremyKun Nov 4 '11 at 23:31
  • $\begingroup$ But this is not in general. This is for a fixed finite number of states, and we know, say, that the number of states needed for the Goldbach conjecture is bounded. And all such 2-state turing machines are known to halt or not halt... $\endgroup$ – JeremyKun Nov 5 '11 at 0:07
  • $\begingroup$ In fact, I don't even care whether it halts or not (knowing whether the Turing machine computing Goldbach's conjecture would halt would solve the conjecture!). I just want to know if one can determine that it computes a specific thing, and if one can minimize the needed number of states to compute that. $\endgroup$ – JeremyKun Nov 5 '11 at 0:14
  • 1
    $\begingroup$ (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. $\endgroup$ – Brian M. Scott Nov 5 '11 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.