0
$\begingroup$

This question already has an answer here:

I have a pretty good handle on what recursive and recursively enume table languages mean with respect to Turing machines and how they relate to one another through my algorithms class. What I don't understand is how these languages relate to the computability of problems, and whether these languages correlate to problems or something else. I'm missing the bridge between the theory and the practical application of theory so abstract, could somebody bridge the gap?

In particular, what does the recursive nature of a language tell us about the problem being considered? Recursive nature being recursive or r.e.

$\endgroup$

marked as duplicate by David Richerby, Evil, jmite, Luke Mathieson, vonbrand Sep 7 '15 at 2:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I want the relation, not to know the difference $\endgroup$ – shane Sep 6 '15 at 23:34
  • 2
    $\begingroup$ The answer to the linked question seems to me to discuss the relationship between languages and problems. Could you edit your question to make it clear what you're looking for beyond what's said there? $\endgroup$ – David Richerby Sep 6 '15 at 23:44
  • $\begingroup$ Definitely a duplicate. I answer the question about what is the relationship: "A language is the formal realization of a problem..." $\endgroup$ – jmite Sep 7 '15 at 0:51
  • $\begingroup$ Edited for clarity? Still a duplicate? $\endgroup$ – shane Sep 7 '15 at 0:53
  • $\begingroup$ Yeah, it's still answered by the other question. A problem is something abstract, it's just an idea. We want to reason about problems formally, so we define a language as a formal model of a yes/no problem. So if the language for a problem is undecidable, the problem is undecidable. The problem IS the language. The language is just how we make the problem concrete. $\endgroup$ – jmite Sep 7 '15 at 0:57