Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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"? –  Srivatsan Nov 4 '11 at 23:24
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... –  JeremyKun Nov 4 '11 at 23:31
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... –  JeremyKun Nov 5 '11 at 0:07
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. –  JeremyKun Nov 5 '11 at 0:14
(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. –  Brian M. Scott Nov 5 '11 at 0:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.