I'm interested in the following problem REG_TM: given a Turing machine, decide whether its language is a regular one.
Of course REG_TM is undecidable (via Rice or direct reduction), but I just read in the Kozen (Automata and Computability) that it is Sigma_3-complete. I'm quite convinced that it's Sigma_3, but I cannot find a proof of completeness. Would anyone have an idea?
In the same vein, is deciding whether the language of a machine is decidable Sigma_3-complete as well ?