# A language is Turing recognizable iff it is a projection of a decidable language

I was wondering how to prove that a language $$C$$ 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 solve this problem or any problem as this kind?

• 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.
– Raphael
Apr 9, 2015 at 6:47

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.