Decidability of whether a language described by Turing machine is regular

Question

I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, namely ones that check for symbol and then move right. If the language is not regular, then simulated FA will eventually come across a string that it cannot process, and give it a FALSE. On the other hand, if the language is regular, FA will successfully accept every string. The problem is that the language has infinite number of strings, and the simulated FA will be checking then forever and never giving affirmative answer. That would make said problem undecidable. Is my reasoning here correct? And if it is, can it be considered a valid proof, or do I need to prove it some other way?

EDIT: The exact wording of the exercise translated as best as I can: You're given a problem of whether language of given Turing machine is regular. Decide whether this problem is decidable and whether is partially decidable. Formally prove your argument.

Answer 1

This language/problem is neither decidable nor partially decidable (r.e). You can use Rice's theorem to prove it. The following proves that the language is not decidable.

"$L$ is regular" is a nontrivial property of recursively enumerable languages since there are regular and non-regular languages which are r.e. For example, $L_1 = \{0^{2n} \mid n > 0\}$ is regular, while $L_2 = \{0^n1^n \mid n > 0\}$ is not regular, but both are r.e. Hence, by Rice's theorem the language $\{\langle M \rangle \mid L(M) \text{ is regular } \}$ is not decidable.

In order to prove that this language is not r.e. you could use Rice's theorem for recursively enumerable index sets.

Answer 2

Your reasoning as is does not exactly show it is undecidable, since you need to show that all Turing machines fail to solve it. Since a set being regular is a non-trivial property, you can use Rice's Theorem to prove the problem is undecidable.

We can make an explicit machine construction to prove that the Halting problem starting with empty input is reducible to your problem. Let $M_{NR}$ be a machine which accepts a non-regular set, such as $\{a^nb^n \mid n \geq 1\}$. The construction takes a Turing machine $M$ as input, and constructs a new machine $M'$ which does the following:

• Given input $x$, first simulate $M$ on empty input.
• If and when $M$ halts, simulate $M_{NR}$ on input $x$. Output the answer that $M_{NR}$ gives.

Here, we see that if $M$ halts on empty input, $M'$ always makes it to the second step, and so $M'$ accepts precisely the language of $M_{NR}$, which is not regular. If $M$ does not half on empty input, $M'$ never makes it to the second step, and so $M'$ accepts the empty set, which is regular. Therefore, $L(M')$ is regular if and only if $M$ does not halt on the empty set. This completes the reduction, such that if your problem were decidable, the halting problem with empty input would be too. But the latter is undecidable, so your problem is necessarily undecidable.