Show that this language is undecidable

312 Views Asked by At

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.