Undecidability of: $|w \in L| \geq 1, L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$

94 Views Asked by At

Let $a_0, a_1 \in \mathbb{N} \setminus \{0\}$ and $L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$ . Let's assume problem $P$ that, language of Turing machine accepts at least one word from language $L$. Using membership problem, is $P$ undecidable?

Membership problem of $w \in L \land L \in unrestricted$, is undecidable but is semi-decidable. Prove of semi-decitability is quite easy by simulating of Turing machine $T$, where $L(T)=L$. But how can we show that $P$ is undecidable?

1

There are 1 best solutions below

0
On

To show that a language over Turing Machine encodings is undecidable, we can use Rice's Theorem, which states that any non-trivial semantic property of Turing Machines is undecidable. Here, our property is "Turing Machine $M$ accepts at least one word from language $L$." We first note that, for every $a_0,a_1 \in \mathbb{N} \setminus \{0\}$, $L$ is nonempty and does not contain every string. For the former, $1^{a_0} \in L$ for any $a_0,a_1$; for the latter, observe that $\varepsilon \notin L$ for any such $L$.

From here, we just need to show that this property is nontrivial. This requires showing that there is a Turing machine that accepts a language satisfying this property, and one that accepts a language which does not satisfy this property. Turing machines accepting the languages $\Sigma^*$ and $\emptyset$ suffice, respectively.