0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I want the relation, not to know the difference $\endgroup$
    – shane
    Commented Sep 6, 2015 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
    Commented Sep 6, 2015 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$
    – Joey Eremondi
    Commented Sep 7, 2015 at 0:51
  • $\begingroup$ Edited for clarity? Still a duplicate? $\endgroup$
    – shane
    Commented Sep 7, 2015 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$
    – Joey Eremondi
    Commented Sep 7, 2015 at 0:57

0

Reset to default