HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Decidability of whether a language described by Turing machine is regular

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
describedregularlanguagedecidabilitymachineturingwhether

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#85231, answer score: 6

Revisions (0)

No revisions yet.