in Theory of Computation retagged by
575 views
0 votes
0 votes
Is every countable language recursive enumerable?
in Theory of Computation retagged by
by
575 views

1 Answer

0 votes
0 votes

No.

Set of all recursive enumerable language is countable. But there are infinitely many infinite languages for which no TM exists.

Out of the languages not recursive enumerable if we take any single language then its countable but not recursive enumerable.

https://stackoverflow.com/questions/26950446/does-there-exist-a-tm-for-all-countable-languages

Related questions