1
$\begingroup$

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?

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

I don't want to spoil the exercise, but I'd try to play with the fact that the property

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

Try to exploit this in your reduction.


Can I use some kind of search algorithm to find a string in it and exclude it?

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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