I'm studying for an exam in theoretical informatics. I have a question for which I can't find an answer. Is every language with the following alphabet decidable:
∑ ={1}
I need to explain why it is or isn't.
I'm studying for an exam in theoretical informatics. I have a question for which I can't find an answer. Is every language with the following alphabet decidable:
∑ ={1}
I need to explain why it is or isn't.
It is not the case that every language of the alphabet is decidable. This is because of the following argument which is based on the fact that not every language over $\{ 0, 1 \}$ is decidable.
Assume for a contradiction that every language over $\{ 1\}$ is decidable i.e. for every language over $\{ 1\}$ there is a TM $M$ which stops on any input and accepts exactly the specified language. Let $L$ be any language over $\{0, 1\}$. Define the function $f: \{0, 1\}^* \rightarrow \{ 1\}^*, f(w) = Dec(1w)$. $f$ is a bijection. Let $L' = f(L)$. We know that we can decide $L'$ and we can build a TM which can perform the function $f$. Thus we can decide $L$ using a TM which first does the mapping $f$ and then uses the TM for language $L'$. Therefore we can decide all languages over $\{ 0, 1\}$. This is a contradiction.