Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$

I would like to know if my proof makes sens. I am using the reduction.

Considering the function $f$ given $<M,w>$ ( where M is a turing machine and $w$ is an entry for $M$) returns the description of the following program:

$N_{M,w}$ = entry x

If x is not of form $0^k1^l$ reject x

If x is of form $0^k1^l$ then we simulate $M$ on the entry $w$

If $M$ accepts $w$ then accept $x''$

Note : $f$ is calculable

If $M$ accepts $w$ then $N_{M,w}$ only accepts words of form $0^k1^l$ then $<N_{M,w}>$ is in language $K$.

If $M$ doesn't accept $w$ then $N_{M,w}$ doesn't accept any words and in particular, doesn't accept any words of form $0^k1^l$. So $<N_{M,w}>$ isn't in $K$

So, $<M,w> \in Acc_{MT} \leftrightarrow$ $<N_{M,w}> \in K$ so $f$ is a reduction of $Acc_{MT}$ to $K$ and since $Acc_{MT}$ is undecidable, $K$ is also undecidable.

Does my proof work, if not what do i need to change, it seems to me that i am just applying a recipe seen in class without really understanding totally.. ?

Thanks a lot.

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Dec 1 '20 at 20:33
  • $\begingroup$ @D.W. Sure updated it so it's not yes or no. $\endgroup$ – codetime Dec 1 '20 at 21:13
  • $\begingroup$ Sharing a copy of your exercise task and asking us to solve it for you is not exactly the kind of question we're looking for, either, as that's unlikely to be of value to anyone else unless they are facing exactly the same task. We'd like to help you learn concepts but I'm not sure that solving that problem for you will do that. $\endgroup$ – D.W. Dec 1 '20 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.