Proving prefix language of a given language is not decidable

714 Views Asked by At

I'm aware that there is a question already about prefixes and decidability but it didn't really help me. I'm given a language L that consists of the strings $R(M)1^n$ such that execution of the Turing machine M with empty input string $\epsilon$ terminates within n steps. I need to prove that the Prefix language $L' = \{w \in \Sigma^* | \exists u \in \Sigma^*:wu\in L\}$ is not decidable. I've tried to reduce it to the halting problem or look for a property that lets me use Rice's theorem but I was unable to reach anything meaningful, what am I missing?