4
$\begingroup$

Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?

$\endgroup$
4
  • 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$
    – quicksort
    Oct 24, 2017 at 13:13
  • 3
    $\begingroup$ How do you describe the language in your input? $\endgroup$ Oct 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$
    – quicksort
    Oct 24, 2017 at 19:35
  • 1
    $\begingroup$ cs.stackexchange.com/q/18010/755 $\endgroup$
    – D.W.
    Oct 25, 2017 at 2:46

2 Answers 2

15
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • 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$
    – Wildcard
    Oct 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$
    – Arno
    Oct 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$
    – Wildcard
    Oct 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$
    – Arno
    Oct 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$
    – Wildcard
    Oct 25, 2017 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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