We'll say the alphabet for the languages is finite, say {0,1}.
3
-
3$\begingroup$ Possible duplicate of cs.stackexchange.com/questions/41963/… Every language is countable, hence not all countably infinite languages are recursive (since we know there are non recursive languages). $\endgroup$– ArielCommented May 13, 2016 at 9:02
-
$\begingroup$ @Ariel Definitely not a dupe of that question. This question asks "Does every X have property Y?" and the other one is "Are there Y's that don't have property X?" $\endgroup$– David RicherbyCommented May 13, 2016 at 14:04
-
1$\begingroup$ Not a duplicate per se, but the answer there explains why every language is countable, which lies at the heart of both questions. $\endgroup$– ArielCommented May 13, 2016 at 14:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Every language over a finite alphabet is countable so your question is just "is every language recursive?" The undecidability of the halting problem shows that there are non-recursive languages.
answered May 13, 2016 at 14:27