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.
$\begingroup$
$\endgroup$
1
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
0
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.
