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