Given a language $L \subset \{0, 1 \}^*\#\{0, 1 \}^*$ and a language $$L'=\{u \in \{0,1\}^* | \textrm{ There is a word }w \in \{0,1\}^* \text{, so } u\#w \in L\}$$
Prove or disprove:
- If $L$ is recursively enumerable, then $L'$ is recursively enumerable.
- If $L$ is recursive, then $L'$ is recursive.
My idea for 1:
Since we know by the definition of $L'$ that for every $u \in L'$, there must be a $w \in \{0,1\}^*$, so $u\#w \in L$. So we can construct a Turing-machine $M_f$, which decides the function $f: \sum ^* \to \sum ^*$ where $\sum^*$ is the alphabet, so $$u \in L' \iff f(u) = u \# w \in L$$
So $L'$ is reducible with $L' \le L$, and because $L$ is recursively enumerable, $L'$ is recursively enumerable.
Regarding the second questions, I would argue the same but I think it is possible to construct a more detailed turing machine. Any hints?