1
$\begingroup$

For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts. Is $X_k$ recursive, recursively enumerable or neither?

I think $X_k$ is NOT recursively enumerable because even if you generate every possible string, and test each one, if you find $k$ strings that M accepts, you still have to check every other string (in case $M$ accepts more than $k$ strings), which means your machine will loop indefinitely, and never find a yes-instance. However I'm not sure how you would show this, initially I thought I could reduce the NHP (Not Halting Problem) to L but that didn't go too well. Any ideas?

$\endgroup$
1
$\begingroup$

Hint: to decide whether $M$ halts on input $w$, consider a new machine $M'$ that rejects every input except $w$ and simulates $M$, otherwise. That's not quite the answer but it should get you close enough.

$\endgroup$
0
$\begingroup$

Please see a related question. Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

Though the question talks about $|L(M)| = 1$ the solution is general enough for any $|L(M)|$.

We can show $L_u \leq X_k$ as following. We reduce $\langle M,w\rangle$ to a Turing machine $M'$ as follows: $M'$ rejects all inputs other than $w$ and some other $k-1$ distinct strings. $M'$ accepts the other $k-1$ distinct strings as mentioned before. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L_u$ iff $M' = f(\langle M,w\rangle) \in L$.

In fact we can prove that $X_k$ is neither RE nor co-RE. This can be done by taking $k$ other distinct strings than $w$ in the above reduction.

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