If you want to make money online : Register now

Is the language of TMs that accept finite languages in $\mathbf{0}'$?

, , No Comments
Problem Detail: 

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?

Asked By : Andrew MacFie
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63418

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback