# Reduce Turing Machine

If $T_n = \{ \langle M \rangle \mid M \mbox{ is a Turing machine and } |L(M)| = n\}$ where $n$ is $0,1,2....$

I need to show that if $n \geq 1$, $T_{n+1}$ reduces to $T_n$. I know I need to create a machine where that machine accepts $|L(M)|-1$ strings, which I could then use to verify with $T_n$. I'm just confused as how to properly do it. Can I use some kind of search algorithm to find a string in it and exclude it?

• Which type of reduction? – Raphael Jul 4 '17 at 5:16
• FWIW, the title is not helpful. Can you formulate a snappy one? – Raphael Aug 3 '17 at 5:04
• See here for some general pointers. – Raphael Aug 3 '17 at 5:05

$$p_M(n,k):\ \mbox{M accepts n in exactly k steps}$$
is decidable. Then, we have that $\langle M \rangle \in T_{n+1}$ iff there are exactly $n+1$ pairs $(n,k)$ satisfying $p_M$.
This approach is unlikely to work: to search, the new TM $N$ would need to run $M$ on some given inputs, but this is risky since $M$ can diverge and "block" the whole execution of $N$. It's safer to work with decidable predicates like $p_M$.