That depends a bit on how the problem is formulated. When stated in full generality, ie "given an arbitrary UTM, decide whether it's a regex finder", it's obviously not decidable.

However, the full expressive power of Turing machines may not be needed. For some classes of grammars/automata, the question whether something is a member of the class can be decided by an automaton, this property is known as automaticity and has origins in the field of descriptive complexity. See for example
http://semukhin.name/autofeed2.pdf

Also relevant, work on the enumeration of regexps, eg
http://arxiv.org/abs/1204.4982

Indeed. See my posts above for a reference to a Karp reduction from VERTEX COLORING (for the automaton version). Previous hardness and non-approximability results for this and related problems were found by Gold (early 70s!), Angluin and Abe.

Myabe also worth mentioning that not all NP-hard problems are created equal. The natural parametrization of SET COVER is W[2]-hard, but there are no decent re-parametrizations known for coloring that give it a place in the W-hierarchy. I know only of one trivial one.

Coloring is still NP-hard when graphs are restricted to be 3-colorable, planar and having maximum degree 4. it seems to be a very hard problem in certain ways.

I guess you're saying that it's still a legitimate subject, and that progress is made by building on previous results. Nobody is disputing that.

But the TFA doesn't mention previous results or even the existence of the field, I have the impression that Norvig is not aware of it. So this is not contributing to the body of knowledge re automata induction, this is recreative CS. Nothing wrong with that per se, but there's also nothing wrong with providing some scientific background.

Btw in the blog post, the approximative approach is motivated by NP-hardness of the exact problem. Given the link (parameter-preserving reduction) with graph coloring already mentioned, the problem can't be approximated in polynomial time with arbitrary error, unless P=NP. This theoretical result is backed up by practical experiments with approximating coloring algorithms, which often find solutions 100% off from the optimal nr of colors. So good luck with that.

Also, informed regular inference is already NP-hard when restricted to DFAs with just 2 states:
http://link.springer.com/chapter/10.1007%2F978-3-642-37064-9_25

Perhaps surprisingly, the problem becomes tractable when the data is `complete', in the sense that it is consistent with just one single automaton (google RPNI).

There's a field called Grammar Induction, and the problem of learning regular languages, aka regular inference, can be considered a subfield. People have been working on this since the '50s. Applications include learning DTDs for XML/wrapper induction, and all kinds of problems in bioinformatics and natural language processing.

There's a strong link with the graph coloring problem, see
http://www.cs.ru.nl/~sicco/papers/alt12.pdf

In this field, the focus is generally on learning FSAs, but these can easily be transformed into regexps. There's work on learning regexps directly, see
http://www.informatik.uni-trier.de/~fernau/papers/Fer05c.pdf

Enjoy.

3) Look at my pussy

There, fixed that for you.

The 'from' header field is for your social security number, not GPS coordinates, you insensitive clod!

..and you're hung like a horse as well!

Today they mount a cyber-terror attack, tomorrow they come back and cut off your Johnson.

You fink zey are kidding, making with ze funny stuff!?

Uhm.. how would that be a bad thing?

Harming puppies? Terrorist.

Paywalling articles? Terrorist.

Say what? Have you ever been to Europe?

I live in the Netherlands and have been (casually) following this case, so here's some background that might be relevant:

Some posters here wondered why this guy agreed to give his DNA. There is some evidence that he is mentally ill: in 2009 he was convicted of stealing a neighbor's car and joyriding while under the influence. He claimed not to be in control of his actions at the time, and that he only came to his senses while in the car. A psychiatrist diagnosed this as a dissociative fugue at the time (he was still convicted). A neighbor of his also recently stated that he has mental problems. So it's quite possible that he doesn't even remember the rape and murder. It's also quite possible that it's simply a lame insanity defense.

I think one of the reasons for this DNA-dragnet was that the area is sparsely populated, and the cities/villages there are tight-knit communities. Many people there are blood-related, so the odds of finding a partial match should be good. It may also be the reason that so many people were willing to participate; they wanted to believe that the perp was an outsider (some still think so). My guess is that some social pressure was involved as well. Anyway, I don't see something like this working in the major cities. Very few people would volunteer, and chances of finding a relative of the perp would be much lower.

Also, there were other DNA tests before, these were done to rule out two suspects - asylumseekers from Iraq and Afghanistan, respectively. They had been fingered in an anonymous letter, possibly with a racist motive. Analysis of the DNA found on the victim pointed to a caucasian anyway (not uncontroversial).

my mom

no, seriously, my mom