Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?
-
2$\begingroup$ There is a fundamental problem with this question. Languages are subsets of $\mathbb{N}$ and there are uncountably many of them. Computational models need to work with finite representations, and in this case there isn't one. $\endgroup$– quicksortOct 24, 2017 at 13:13
-
3$\begingroup$ How do you describe the language in your input? $\endgroup$– Paŭlo EbermannOct 24, 2017 at 19:29
-
1$\begingroup$ @jjmontes Of course. But in order for the statement to make sense as a decision problem, you have to specify how the input is given, and that requires to specify a way to write all of them. $\endgroup$– quicksortOct 24, 2017 at 19:35
-
1$\begingroup$ cs.stackexchange.com/q/18010/755 $\endgroup$– D.W. ♦Oct 25, 2017 at 2:46
2 Answers
As quicksort notes in his comment, languages are infinite objects and it is not possible to feed them to Turing Machines.
So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language.
Unfortunately, even for context-free grammars it is undecidable whether their language is regular.
Bar-Hillel, Perles, Shamir. On formal properties of simple phrase structure grammars. (1961) doi 10.1524/stuf.1961.14.14.143
Contrary to the claims by Hendrik Jan and quicksort, the question makes perfect sense as asked. A Turing machine uses infinite tapes, so can we can indeed process an arbitrary language as input, written out on the input tape.
However, any finite prefix of the language tells us nothing about whether or not the language is regular. Thus, the problem is not decidable, and moreover, not even semi-decidable either way.
The best thing we can do is going through all regular languages (which we can effectively generate) and compare them to the input. This yields an algorithm that will say not regular infinitely often if and only if the language is indeed not regular. This is just a way of saying that being regular is a $\Pi^0_2$-complete property of languages.
-
2$\begingroup$ It doesn't really make sense to talk about Turing machines given infinite input. Infinite output, yes—as defined by a finitely expressed Turing machine that can run infinitely. But input? How do you explicitly define the input tape? $\endgroup$– WildcardOct 25, 2017 at 1:29
-
$\begingroup$ The input to a Turing machine is naturally an infinite sequence over the alphabet, namely whatever symbols are written on the tape at the start of the computation. If we actually want a finite input, then we need to code it somehow, typically by having a finite consecutive block of non-blank symbols, and blank everywhere else. If we are working with infinite input, no coding is necessary. $\endgroup$– ArnoOct 25, 2017 at 8:20
-
$\begingroup$ Have you actually read Turing's paper? What you are saying does not make sense. There are an infinite number of possible inputs to a Turing machine; every one of them is itself finite. Just as there are infinity natural numbers but each natural number is finite. $\endgroup$– WildcardOct 25, 2017 at 8:43
-
$\begingroup$ I have read Turing's paper, and know that he discusses eg using real numbers as input to Turing machines. [I have also published a dozen papers or so involving Turing machines having infinite sequences as input.] If the tapes of a TM were not infinitely long, we'd be talking about a finite automaton instead. Since the tapes are infinitely long, they can hold an infinite sequence of symbols. What is there not to understand about that? $\endgroup$– ArnoOct 25, 2017 at 8:55
-
$\begingroup$ Well, fine—since, as you say, any finite prefix of the language tells us nothing about whether it is regular or not, I suppose we are really in agreement. The point I was making is more that the entire tape will never be input into the Turing machine, i.e. there will never be a point where the entire tape has been read and has factored into the TM's behavior. I wouldn't call the starting content of an infinite tape "input" when it is obvious it cannot all be read in; I would call it the "starting tape." $\endgroup$– WildcardOct 25, 2017 at 9:15