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 ?


Your Answer

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

Browse other questions tagged or ask your own question.