-2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.