# Prove that the language Cats-Vs-Dogs is undecidable

Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not both.}.

Rice's theorem will give a direct and simple proof for this question.

If you have not yet learned Rice's Theorem you can use a Turing reduction here, which is essentially a proof by contradiction. We want to show that some undecidable problem can be reduced to Cats-Vs-Dogs, which would mean that if we could decide Cats-VS-Dogs, we could decide that undecidable problem, a contradiction! Let's use the halting problem. We know that the language {<M,w> | M halts on w} is undecidable.

Suppose Cats-VS-Dogs is decidable and let T be a decider for it. Construct the TM S as follows:

On input: <S',w>
$$\quad$$ Construct Machine M as follows:
$$\quad\quad$$ On input x:
$$\quad\quad\quad$$ if x is 'dogs' ACCEPT
$$\quad\quad\quad$$ run S' on w
$$\quad\quad\quad$$ if x is 'cats' ACCEPT
$$\quad$$ Run T on <M>
$$\quad$$ If T accepts REJECT otherwise ACCEPT

Notice that if S' halts on w then L(M) contains both 'dogs' and 'cats,' so when we run T on <M> T will reject since it decides the Cats-VS-Dogs problem, in this case S accepts. On the other hand if S' does not halt on w then L(S') contains 'dogs' but not 'cats' since running S' on w will never halt. In this case when running T on <M> T will accept, so S rejects. Then L(S) = {<M,w> | M halts on w}.

Also notice that the machine called M is never run by S, just constructed and its description passed to T. Since T decides Cats-VS-Dogs T always halts, so S always halts too. Then S decides {<M,w> | M halts on w} and we have obtained our contradiction!