Reduction from $A_{TM}$ to $L$ where $w_1$ is prefix of $w_2$

127 Views Asked by At

I'm trying to prove by reduction that $L$ is undecidable: $L=\{\langle M \rangle \mid M \text{ is a turing machine and there are two words } w_1,w_2\in L(M) \text{ such that }w_1 \text{ is prefix of }w_2 \text{ and also the length of }w_1 \text{ is smaller then the length of }w_2\}$

Attempt:

I tried to do reduction from $A_{TM}=\{\langle M,w \rangle \mid M \text{ accepts }w\}$, now to find a function $f:A_{TM}\to L$, my difficult is how to build this function. any help?

$f:(⟨M,w⟩)=⟨M,w1,w2⟩ $is a prefix of $w_2$ and $|w_1|<|w_2|$ will work?

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose $D$ is a decider for $L$.

ATM = "On input <A, s>:
        1) M = "On input <w>
                10) Simulate A on s
                20) if A accepts s
                30)     if w = '0' or w = '01'
                40)         accept
                50)     else
                60)         reject
                70) else
                80)     reject
        2) if D accepts <M>
        3)     accept
        4) else
        5)     reject

D accepts $\langle M \rangle \; \iff \langle M \rangle \in \; L \iff A$ accepts s

If D decides L then ATM decides $A_{TM}$
Since $A_{TM}$ is not decidable, L is not decidable.

Note the structure of the reduction.
In constructing M, you just pick w so that $M \in L$.