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.
Asked
Active
Viewed 133 times
-1
-
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, use MathJax. – dantopa Jun 15 '19 at 07:23
1 Answers
0
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.
sebastian
- 2,130