Using reductions to prove unsolvable sets

Question

Let CaDo = {<M> | M accepts at least five strings that contain CAT as a substring and

rejects at least five strings that contain DOG as a substring>. Is CaDo decidable? Justify your answer.

Answer 1

Recall the undecidability of ATM, specifically that ATM = { <M,x> | M accepts given input x } is undecidable. We now construct a Turing Machine M_atm which will accept inputs that are in ATM and will reject inputs that are not in ATM, using a TM that decides CaDo, M_CaDo.

For a given input <M,x> to M_atm, consider constructing Turing Machine M', which when given an input x' that contains CAT, will replace x' with x on the tape, then run M. On the other hand, given any other input x' that does not contain CAT, M' will still replace x' with x, but now will accept if M rejects and reject if M accepts (I'll call it inverting the output of M - note that if M loops on x, so does M' on all inputs x'). In other words, no matter what input M' receives, it does the equivalent of running M on x, except it also inverts the output of M if M halts on x and x' does not contain CAT. Now consider running M_CaDo on the input <M'>. We have three cases to consider:

1. M accepts given x as input. In this case, there are at least five inputs x' that contain CAT (e.g. CAT1, CAT2, CAT3, CAT4, CAT5) for which M' will accept, since M accepts x and any x' containing CAT will effectively return whatever M returns when given x. There will also be at least five inputs x' that contain DOG (e.g. DOG1, DOG2, DOG3, DOG4, DOG5) for which M' will reject, since M accepts x and M' will reject when M accepts x since x' does not contain CAT. In this case, M_CaDo will accept input <M'>.
2. M rejects given x as input. In this case, there are no inputs x' that contain CAT for which M' will accept, since M rejects x and all inputs x' that contain CAT will lead to M' outputting whatever M does, which is to reject. Thus, M_CaDo will reject input <M'>.
3. M loops given x as input. In this case, all inputs x' will lead to M' looping, as regardless of whether x' contains CAT or not, M will loop and so will M' (by definition of M'). Specifically, M' does not accept any strings containing CAT, so M_CaDo will reject input <M'>.

We therefore have that M_CaDo accepts M' if and only if M accepts x (since if M does not accept x, i.e. M loops or rejects on x, we saw that M_CaDo rejects M'). This leads us to our definition of M_atm: On input M, construct M' as described above, then output whatever M_CaDo outputs on M'. M_atm will accept if M accepts x and will reject if M does not accept x, so we have found a TM that decides ATM, proving that ATM is decidable. However, this is a contradiction. Our assumption was that CaDo was decidable, i.e. M_CaDo exists, so that assumption must be false, meaning no such M_CaDo exists, implying that CaDo is undecidable.