I need a combination programmer and semanticist

[Voyager]

@ultrafilter

Yes, that’s what I mean. I don’t completely understand all the details, but it looks like the problem of deducing a grammar from valid and invalid strings is at least as hard as several cryptographic problems that are widely believed to be intractable.

Whoa. NP hard problems have nothing to do with the halting problem. The halting problem is undecidable, NP hard problems are algorithmic and decidable - they just take a lot of time in the worst case. It doesn’t even mean that the problem is hard in practice - I have a paper in Transactions on Computers that shows a particular NP hard problem is actually near linear for lots of practical cases.

However you are correct about parsing grammars. I can think of problems that it can reduce to, so I am pretty sure it is NP hard. I haven’t done this kind of thing in a long time, so if you doubt yourself I would have to do a tad of research, but look up NP complete and I bet you’ll find problems just like this, if not this one.

[ultrafilter]

From here:

The Kearns-Valiant theorem, that PAC-learning an arbitrary regular language is as hard as breaking RSA. This is really what Chomsky meant to say but didn’t when he proposed his famous Poverty of the Stimulus argument about language learning in infants.

Breaking RSA doesn’t appear to be NP-hard, so my initial claim was a bit strong, at least for regular languages.

[Poor_College_Student]

As long as we’re doing xkcd’s:

is appropriate.

[iamthewalrus_3]

@iamthewalrus(:3=

By “learning grammars” do you mean “deducing a grammar by observing instances of valid and invalid strings in that grammar”? If so, off the cuff, that sounds like a generalization of the halting problem.

I was thinking that you’d never be able to know if you’d actually defined the grammar that you care about, you’d only be able to generate one that was consistent with what you’d seen so far. That seems unsolvable to me. But maybe that uncertainty doesn’t matter.

[ultrafilter]

@iamthewalrus(:3=

I was thinking that you’d never be able to know if you’d actually defined the grammar that you care about, you’d only be able to generate one that was consistent with what you’d seen so far. That seems unsolvable to me. But maybe that uncertainty doesn’t matter.

If you’re going to do any kind of meaningful statistics or machine learning, you have to assume that the data you’ve seen is representative of the data you haven’t seen. So it matters, but on a deeper level than you really need to worry about on a day-to-day basis.