This question already has an answer here:

  1. Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?

In other words, let $R$ be the set of languages (including languages over alphabet having infinite symbols). For all $L$, belonging to $R$, that are not recursively enumerable, can it be said that $L$ is uncountable?

  1. Is any language (in the set $R$ defined above) recursively enumerable and uncountable?

NB : I am asking about the (un)countability of a language (set of strings) and not a set of languages.


marked as duplicate by David Richerby complexity-theory Aug 20 '18 at 22:30

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.


Definition: a string over an alphabet $A$ (of finitely many symbols) is a finite sequence of symbols in $A$.
Definition: a language over an alphabet $A$ is a set of strings over $A$.

  1. Is every language which is not recursively enumerable, uncountable?

No. Any language is a subset of the complete language $A_*$, the set of strings over $A$, which is a countable set. So, in fact, any language is a countable set of strings.

  1. Is there any language which is recursively enumerable and uncountable?

No. The reason is the same as above.

The answers and the reasons behind them remain the same even if we allow $A$ to be a countably infinite set.

These two questions are not the same as the questions in Is there a non-recursive and uncountable language L?. However, the answer with its the reasoning are the same as [the answer to that question](https://cs.stackexchange.com/a/55855/91753.

OP just updated the question. So the only case left unanswered is when $A$ is an uncountably infinite set.

In that case, the definition of a language being recursively enumerable such as the one at wikipedia becomes inapplicable since all (common) models of Turing machines require the number of symbols to be finite (or at most countably infinite). To continue the discussion, we will need to make a new list of definitions for the Turing machines of the extraordinary kinds(which is not the Turing machines we usually talk about) or even other kinds of machines for hypercomputation and what is means by a recursively enumerable language with respect to those machines. That would be too large a scope that I would prefer not to go into in this answer.

  • $\begingroup$ My question was unclear. Apologies. I meant to ask , what if the alphabet is of infinite letters. I will edit the question. $\endgroup$ – Swapna Sarit Aug 20 '18 at 20:18
  • $\begingroup$ @SwapnaSarit, I just updated my answer. $\endgroup$ – Apass.Jack Aug 20 '18 at 21:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.