3
$\begingroup$

I was wondering how to prove that $C$ (which is a language) is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not know how to prove this kind of questions, is there any help to help me solve this problem or any problem as this kind.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What have you tried and where did you get stuck? What exactly don't you know? It's unlikely that you got to an exercise such as this without knowing how to prove an equivalence, for example. $\endgroup$ – Raphael♦ Apr 9 '15 at 6:47
3
$\begingroup$

There are two directions here. One is trivial: if $C$ is indeed of the above form, then it is clearly recognizable: given $x$ just run $D$ on all possible $y$'s in a dovetailing manner (see, e.g., here, or search in this site).

The other direction is less obvious, but also not too difficult: Assume that $C$ is recognizable. Then, there exists a machine that halts and accepts any $x\in C$. Thus, you can write the sequence of configurations of $M$ on input $x$, and this sequence is finite! This sequence will be the $y$ that exists if $x$ is in the language. You should be able to complete the details from here.

|cite|improve this answer
$\endgroup$

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.