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?

  • 0
    *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"?2011-11-04
  • 0
    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...2011-11-04
  • 0
    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...2011-11-05
  • 0
    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.2011-11-05
  • 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