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?

  • $\begingroup$ 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$. $\endgroup$ – platty Nov 30 '18 at 10:12
  • $\begingroup$ I edited the question, is it better? $\endgroup$ – nocturne Nov 30 '18 at 10:16
  • $\begingroup$ I think so. Is $P$ supposed to be a language of Turing Machine encodings, and the question is whether $P$ is undecidable? $\endgroup$ – platty Nov 30 '18 at 10:16
  • $\begingroup$ 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$ $\endgroup$ – 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.


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.