0
$\begingroup$

Question: we have the following language: $$A = \{\langle M \rangle :| L( M)| < \infty \text{ and } M\text{ is a Turing machine}\}$$ where $\langle M\rangle$ is the encoding of $M$ and $L(M)$ is the language accepted by $M$. Prove $A$ is a decidable language or not.


My idea was to use reduction on this but I can't find the proper one and I don't even know if it is decidable or not.

$\endgroup$
3
  • $\begingroup$ This problem is undecidable, and in fact it is $\Sigma_2^0$-complete, i.e., $L$ is not even recursively enumerable. $\endgroup$ Jul 8, 2022 at 15:29
  • $\begingroup$ @ReijoJaakkola Thank you. Can you please help me with proving it? $\endgroup$
    – ArithEgo
    Jul 8, 2022 at 15:49
  • $\begingroup$ Hint: Consider a Turing machine $T'$ that ignores its input, simulates some other Turing machine $T$ on some input $x$, and then halts and accepts. What can you say about $|L(T')|$? $\endgroup$
    – Steven
    Jul 9, 2022 at 12:43

1 Answer 1

1
$\begingroup$

We can reduce from $A_{TM}$ to prove $A$ is undecidable and also from $\overline{A_{TM}}$ to prove $A$ is unrecognizable. We proceed with the first claim. I recommend you pause here and think about how it could be done before moving forward. The core idea is excatly what Steven suggested that is to specify a Turing machine $M'$ to simulate another Turing machine $M$. (in the case of reduction from $A_{TM}$, the machine-input pair $\langle M, w \rangle$ has to be manipulated by $M'$ such that $M'$ accepts finitely many strings if and only if $M$ accepts $w$.) We can describe $M'$ informally as follows:

  1. On input $n \in 1^+$ (namely reject all but unary representations)
  2. Simulate $M$ on $w$ for at most $n$ steps. If $M$ halted and accepted during simulation, reject $n$. Otherwise accept $n$.

If $M$ accepts $w$ after $k$ steps, $L(M')$ would be $\{1, 2, \dots, k - 1\}$. Otherwise, $L(M') = \mathbb{N}$. Therefore $\langle M, w \rangle \in A_{TM} \iff M' \in A$ or $A_{TM} \leq_m A$. Similarly by swapping "accept" and "reject" in the description of $M'$, we obtain the mapping reduction $\overline{A_{TM}} \leq_m A$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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