Check whether 2 languages are Turing recognizable or co-Turing recognizable

Question

I have these 2 languages

A = {<M> | M is a TM and L(M) contains exactly n strings }
B = {<N> | N is a TM and L(N) contains more than n strings }

I believe that these 2 are undecidable, but I am not sure whether they are Turing recognizable or co-Turing recognizable.

Answer 1

B is Turing recognizable since we can interleave executions of M on all possible input tapes. If more than n of the running instances of M ever halt-accept, then halt-accept.

We know that A cannot be Turing-recognizable because, if it were, the language B' = {<N> | N is a TM and L(N) contains no more than n strings } would be Turing-recognizable (we could interleave the execution of recognizers for 1, 2, ..., n and halt-accept if any of those did). That would imply both B and B' were decidable since B' must be co-Turing recognizable.

If A were co-Turing recognizable, we could recognize machines that accept a number of strings different than n. In particular, let n = 1. We can run the recognizer for machines whose languages contain other than n strings on a TM constructed to accept L(M) \ {w} for every possible string w. At each stage, we run one step of all existing machines, then construct a new machine, and repeat, thus interleaving executions and ensuring all TMs eventually get to run arbitrarily many steps.

Assuming |L(M)| = 1, exactly one of these TMs will halt-accept (the one that removes the only string in L(M)) and the rest will either halt-reject or run forever. Therefore, a recognizer for |L(M)| != 1 can be used to construct a recognizer for |L(M)| = 1. This generalizes to |L(M)| != k and |L(M)| = k by subtracting all possible sets of k input strings.

Therefore, if A were co-Turing recognizable, it would also be Turing recognizable, thus decidable. We already know that's wrong, so we must conclude that A is not co-Turing recognizable; nor is it Turing recognizable.