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

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?

• You don't include a condition in the set-builder notation. What is this supposed to say? It's also unclear what you mean by $L \land L$. – platty Nov 30 '18 at 10:12
• I edited the question, is it better? – nocturne Nov 30 '18 at 10:16
• I think so. Is $P$ supposed to be a language of Turing Machine encodings, and the question is whether $P$ is undecidable? – platty Nov 30 '18 at 10:16
• Question is whether the P is undecidable. Problem P is undecidable when is not decidable which means we can construct a Turing machine $T$, where it decides whether it accepts $w \in L$ and rejects $w \in \sum^* \setminus L$ – nocturne Nov 30 '18 at 10:22

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.