1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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