# Is a set of TM deciding specific length of language reducible?

For instance, if we know a language $L_1 = \{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n \}$ is decidable, can we prove that $L_2 = \{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n-1 \}$ is also decidable? In other words, prove $L_2$ reduces to $L_1$.

• Your "in other words" formulation would be more reasonable since $L_1$ and $L_2$ are both undecidable by Rice's theorem. – Willard Zhan Nov 28 '16 at 8:46
• Putting $n$ to $n-1$ does the trick, doesn't it? – Eugene Nov 28 '16 at 9:14
• @Eugene I think that $n$ is a constant. – Yuval Filmus Nov 28 '16 at 10:00
• What have you tried? Where did you get stuck? We want to help you solve the problem on your own rather than solving it for you. – Yuval Filmus Nov 28 '16 at 10:01

Here is a similar example, to get you started. Let $L_n$ consist of all encodings of Turing machines that accept some string of length $n$.

Claim: $L_{n-1}$ reduces to $L_n$.

Proof: Let $M$ be an input to $L_{n-1}$. Construct a new machine $M'$ which on input $x$, if $x$ starts with a zero then $M'$ rejects, and if $x=1y$ then $M'$ simulates $M$ on $y$. Then $\langle M \rangle \in L_{n-1}$ iff $\langle M' \rangle \in L_n$ (exercise).

Your proof will be different, but the proof technique will be similar.