# Show that the language is undecidable

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.

• 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.
– D.W.
Commented Sep 10, 2023 at 7:50

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