# If $L$ is recursively enumerable (or recursive) then so is $L′$

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:

1. If $L$ is recursively enumerable, then $L'$ is recursively enumerable.
2. 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?

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! Nov 25, 2017 at 20:56

## 1 Answer

The second item is in fact false. Consider the language $L$ consisting of $u\# w$ such that the $u$th Turing machine halts within $w$ steps. This is recursive, but $L'$ is the language corresponding to the halting problem.