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?

  • $\begingroup$ 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! $\endgroup$ – Raphael Nov 25 '17 at 20:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.