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.

  • $\begingroup$ Well any language that is described by Turing machine. So I guess every recursively enumerable language. $\endgroup$ – querti Dec 9 '17 at 18:12
  • $\begingroup$ Could you describe in set theoretic terms what language/problem you want to prove to be decidable? Are you trying to prove that the language $\{\langle M \rangle \mid L(M) \text{ is regular } \}$ is decidable? $\endgroup$ – fade2black Dec 9 '17 at 18:12
  • $\begingroup$ You write "I am trying to prove decidability of problem whether language described by Turing machine is regular.". So, what would be input to your decider? A language? If so, how do you encode languages (in particular infinite)? $\endgroup$ – fade2black Dec 9 '17 at 18:18
  • $\begingroup$ The language would be encoded as Finite automaton. The strings from the language would be generated one by one by the Turing machine describing the language and tested on the automaton $\endgroup$ – querti Dec 9 '17 at 18:21
  • $\begingroup$ "The language would be encoded as Finite automaton". Finite automata would "encode" only regular languages. How would you encode non-regular languages? Non-CF, non-r.e languages? But as far as I understand your decider takes any language and decides if that language is regular, right? $\endgroup$ – fade2black Dec 9 '17 at 18:24

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.


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.


Your Answer

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

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