Show the projection of decidable language is Turing-recognizable

decidabilityturing-machines

Sipser's text on theory of computation, second edition, exercise 4.17, contains the following exercise:

"Show C is Turing-recognizable if and only if there is a decidable language D where
$C=\{x|\exists y \langle x,y\rangle \in D\} \text{ with }x,y \in \Sigma^*$"

Here $\langle x,y \rangle$ is an encoding of the pair of strings x,y.

I cannot solve this; I cannot see why it is true. It seems you would have to run the decider on all possible values for y (an infinite number of trials) before you know if x is in C. What am I missing?

Best Answer

A language $C$ is Turing-recognized by (aka semi-decided by) Turing machine $T$ if and only if $C = \{s \in \Sigma^* \mid T$ halts when given input $s\}$. $C$ is Turing-recognizable (aka semi-decidable) if and only if there is some $T$ which Turing-recognizes it.

Suppose $C$ is Turing-recognizable. Let $T$ be a Turing machine which recognizes it. Let $D = \{\langle s, n \rangle \mid s \in \Sigma^*$, $n \in \mathbb{N}$, and when $T$ is run for $n$ steps on input $s$, it halts$\}$. Clearly, $D$ is decidable. Then $C = \{s \mid \exists n (\langle s, n \rangle \in D)\}$.

Conversely, suppose that $D$ is decidable and $C = \{x \mid \exists y (\langle x, y \rangle \in D)\}$. Then consider the Turing machine $T$ which, given input $x$, iterates through each $x$, one by one, to check if $\langle x, y \rangle \in D$, stopping once it finds such a $y$. Then $T$ Turing-recognises $C$.