Question: Is the following statement true or false?

If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

I thought that since every language is automatically of type 0, it follows that $A \in RE$, and since RE is closed under the Kleene star operator, it follows that $A^* \in RE$ and therefore semi-decidable.

However the solution says it's not true and uses the following counterexample:

If $A = \{1^n0 | 1^n \not\in H'\}$, where H' is the unaryly coded halting problem. Since $\overline{H} \leq A$, A is not semi-decidable. If $A^*$ were semi-decidable then so would be $A^* \cap \{1\}^* = A$, since $\{1\}^*0$ is semi-decidable and RE is closed under intersection, which is a contradiction.

Since I don't fully understand that line of reasoning, could someone please tell me what's wrong with my argumentation?


It is not true that every language is recursively enumerable ("type 0").

Proof 1. Every RE language is semi-decided by some Turing machine. There are only countably many Turing machines (each one can be coded as a finite string, or an integer) but there are uncountably many languages. Therefore, there are uncountably many languages that are not RE.

Proof 2. If a language and its complement are both semi-decidable, they are, in fact, both decidable. The halting problem is semi-decidable. If the complement of the halting problem were semi-decidable then both it and the halting problem would be decidable. But we know that the halting problem is not decidable. Therefore, the complement of the halting problem is not semi-decidable.

  • $\begingroup$ Thanks a lot for your comment. I thought that every language should in theory be producible by a grammar and since every grammar is a type 0 grammar and RE is the class of languages that are produced by type 0 grammars that would imply that all languages are in RE. $\endgroup$ Feb 13 '15 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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