Show the projection of decidable language is Turing-recognizable

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?

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$$.

• t must be frustrating to try to explain this to someone like me. In the second of these three paragraphs, it seems that the point is to show that a decider for encodings <x,y> exists. The comment says that D is decidable and, yes, I can see that, but it is not a decider for encodings <x,y>, it is a decider for encodings <x,n> where n is a natural number. Given y, how do you fix n? – Nov 9, 2021 at 21:54
• @AnnaNaden No worries. If I didn’t want to explain this to you, I wouldn’t be on this website. The trick here is to encode numbers as strings. Take some $a \in \Sigma$. Then formally, we actually have $D = \{\langle x, a^n \rangle \mid$ Turing machine $T$ halts on input $x$ in $n$ steps$\}$. We’re just encoding $n$ as the string $a^n$ - the string of $n$ $a$s. So this is actually an important technical detail I glossed over. Nov 9, 2021 at 21:58
• So we are talking about showing that if a recognizer for x exists then a decider for <x,y> exists, right? It seems we have a decider for $<x,a^n>$. Isn't that a different language from <x,y>? Nov 9, 2021 at 22:09
• If we knew the maximum number of steps required to recognize any string x then we could construct a determiner for <x,y> by running the x recognizer for just that many steps. Is that the solution? Is the number of steps required to recognize a string bounded? I don't think so... consider the language $w#w$ where w is any string. It's recognizable but there seems to be no limit on the number of steps required to recognize it Nov 9, 2021 at 22:39
• @AnnaNaden If $T$ is a recognizer of $C$, then define $D = \{\langle x, a^n \rangle \mid T$ halts on input $x$ in $n$ steps$\}$. We can construct a decider for $D$ as follows: To decide whether $s \in D$, first determine whether $s$ can be written in the form $\langle x , a^n \rangle$ for some (necessarily unique) $n$ and $x$. If not, halt and return $false$. If so, attempt to run Turing machine $T$ on input $x$ for exactly $n$ steps. If we were able to get through all $n$ steps and ended in a halting state, return $true$; otherwise, return $false$. This is the decider for for $D$ as defined. Nov 9, 2021 at 22:41

What you are missing is the fact that you only need to show that there is a Turing machine $$M$$ which accepts every string in $$C$$; notice that we do not require that $$M$$ should halt also on those strings which are not in $$C$$. Turing-recognizability is weaker than decidability.

• Given an x in C, don't we have to run the decider on a string <x,y> in order for halting to take place? How do we know what string to choose for y? I guess there are two machines in this problem - the recognizer for C and the decider for D... I don't understand why we know that the first of these two machines exists. If the recognizer didn't exist, I guess we need to show that would imply that the decider doesn't exist. Is this the right way to look at it? Nov 9, 2021 at 20:32
• And we would need to show that if the recognizer does exist then the decider exists. How can we construct the decider from the recognizer? Nov 9, 2021 at 21:07
• I think that the answer of Mark Saving answers both of these questions. Nov 9, 2021 at 21:11