In this question it is asked, "Is the language of TMs that accept finite languages Turing-recognizable?". It turns out this language $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not. I ask this: We know that the halting problem is Turing-reducible to $L$ but is $L$ Turing-reducible to the halting problem?
1 Answer
$\begingroup$
$\endgroup$
Your language $L$ is usually known as Fin or FIN, and is $\Sigma_2$-complete; see for example lecture notes of Cohen Wallace. Since the halting problem is in $\Sigma_1$, it follows that $L$ cannot be reduced to the halting problem.