Turing recognizable -decidable languages- - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T20:25:57Z https://cs.stackexchange.com/feeds/question/41156 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/41156 3 Turing recognizable -decidable languages- Optimistic https://cs.stackexchange.com/users/30395 2015-04-08T23:06:54Z 2015-04-09T06:46:42Z <p>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.</p> https://cs.stackexchange.com/questions/41156/-/41159#41159 3 Answer by Ran G. for Turing recognizable -decidable languages- Ran G. https://cs.stackexchange.com/users/157 2015-04-09T02:32:22Z 2015-04-09T02:32:22Z <p>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., <a href="https://cs.stackexchange.com/a/30005/157">here</a>, or search in this site).</p> <p>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 <em>finite</em>! This sequence will be the $y$ that exists if $x$ is in the language. You should be able to complete the details from here.</p>