Mark Gritter (markgritter) wrote,
Mark Gritter

DFA's aren't easy

A blog entry on "Open Problems That Might Be Easy" mentions this one:
Given a DFA, does it accept a string that is the binary representation of a prime number--- is this decidable?

I think this is sort of a tricky question in that it sounds simple but actually asks for very deep insights. To solve it you might have to know something about prime numbers which is also an open problem!

How hard are DFAs? After all, we have the pumping lemma which helps us prove that languages aren't regular. But, your computer is actually equivalent in power to a DFA (if we disconnect it from the Internet.) It has only finitely many states, and so the languages it can recognize are regular. So imagine this problem as "how can I tell whether a computer program, running on a Windows Server 2012, on a eight-core machine with 256GB of memory, ever accepts a prime number?" We're talking an unimaginably large number of states--- does it still seem reasonable that there's a computable way of analyzing its behavior?

But, we do have the pumping lemma. So if we could characterize that there is always a prime number of the form a ## ## c, that might answer the question in the affirmative for any DFA for which we could identify its "sufficiently long" strings. But this is obviously false without further qualification--- take a = 1, b = 0, c = 0. If we use [math]a=1111...1111, b=1, c=1[/math] then the answer may depend on the existence of very large Mersenne primes. So it may be possible to write a DFA for which the answer "does it accept any primes" provides a deep number-theoretical result.
Tags: complexity, mathematics
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.