-2
$\begingroup$

Consider the language L = {< M >| M accepts iff input length is divisible by 3}. I'm supposed to use reduction to show that the language is undecidable. I tried proving it but didn't know what to do.

$\endgroup$
1
  • $\begingroup$ We discourage "here is an (exercise-style) task, I don't know how to start" style questions, as they are unlikely to be useful to others in the future. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Commented Sep 10, 2023 at 7:50

2 Answers 2

1
$\begingroup$

What languages are you familiar with? Are you familiar with the fact that $ALL_{TM}=\{\langle M\rangle : L(M)=\Sigma^*\}$ is not decidable? If so try a reduction from $ALL_{TM}$ where given a machine $M$, construct a machine $M^3$, such that $w=w_1\cdot w_2\cdots w_k$ is a accepted by $M^3$ iff $|w|(\mathrm{mod}\ 3)=0$ and $w[i,\infty)$ is accepted by $M$ for all $i=0,1,2$, where $w[i,\infty)$ is the suffix $w_i\cdot w_{i+1}\cdots w_k$.

$\endgroup$
1
$\begingroup$

This follows immediately from Rice's theorem. However, if you don't know that theorem yet and you're asked to prove it by an explicit reduction, see oleshkowitz's answer.

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