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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.