1
$\begingroup$

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?

$\endgroup$

2 Answers 2

0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? – $\endgroup$
    – Anna Naden
    Nov 9, 2021 at 21:54
  • $\begingroup$ @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. $\endgroup$ Nov 9, 2021 at 21:58
  • $\begingroup$ 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>? $\endgroup$
    – Anna Naden
    Nov 9, 2021 at 22:09
  • $\begingroup$ 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 $\endgroup$
    – Anna Naden
    Nov 9, 2021 at 22:39
  • $\begingroup$ @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. $\endgroup$ Nov 9, 2021 at 22:41
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Anna Naden
    Nov 9, 2021 at 20:32
  • $\begingroup$ 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? $\endgroup$
    – Anna Naden
    Nov 9, 2021 at 21:07
  • $\begingroup$ I think that the answer of Mark Saving answers both of these questions. $\endgroup$ Nov 9, 2021 at 21:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .