Lambda the Ultimate

My friend argued that Chomsky is regarded as very important for CS.

Well, without weighing in on the actual issue of Chomsky's continued importance myself, I have to say that I do hear his name mentioned by non-CS academics a lot in connection with CS, in the same way your friend did. Those who are in linguistics, philosophy or math (and probably the older ones at that) might have a sense of the connection, albeit without a full understanding of the situation since the 60s or 70s.

And of course, many academic acquaintances in other disciplines, further afield, have no real sense for CS at all, at least the way LtUers would think of it. (A request for my expert help in downloading a JPG from a browser window comes to mind :) .)

(As an aside, I'm always surprised that algebraists don't have more experience with Kleene algebras or combinatory algebras: despite all the vaunted abstraction, the ones I meet seem pretty focused on generalizations of numeric-style structures. CAs perhaps don't have much to offer outside computability issues, but I'd have thought that algebraic characterizations of automata and languages would be more popular among mathematicians, being not too different from the usual rings and such.)

My friend argued that Chomsky is regarded as very important for CS.

As a somewhat lapsed linguist, my somewhat more cynical assessment of this meme is that it is most often invoked to one of three ends:

• To praise the authority of Chomsky, the man, especially as a bolster for his political views.
• To legitimize the importance of linguistics as a discipline, e.g. What has linguistics ever accomplished? Well, Chomsky has made important contributions to CS.
• As an apologia for linguists who want to ignore mathematical and computational models of language, e.g. Chomsky made important contributions to CS and mathematical models of language, and he says that stuff isn't really that important to understand language, so I don't need to deal with it.

Though the Chomsky Hierarchy is a significant constribution to in the history of CS, my own assessment is that overall Chomsky will end up being viewed not unlike Skinner, who he "did in": admired as an influential genius, but with most of his specific ideas discarded or modified.

A colleague of mine has recently retired, and was getting rid of his considerable collection of papers. Amongst other things in there, I got myself an original copy of Chomsky's "Syntactic Structures".

I wonder if Chomsky would have received the Turing Award for his work if he had been a computer scientist.

If Chomsky had been a computer scientist, he would almost certainly have won a Turing award. Part of the reason for this would have been that he would have done in computer science what he did for linguistics, revolutionizing the way the subject was done, and spawning an influential community of disciples. Almost independently of the actual merits of his later work, the disciples would have given him the prize.

On top of the mathematical content, Chomsky has a series of claims about how language is and how it should be studied. These are no less revolutionary than the purely formal ideas, and have again been hugely influential, but not always for the good. The minority of linguists who insisted on collecting and working with samples of naturally occurring language were seen by some in Chomskyan majority as quaint and behind the times, and another minority (influenced by logicians, and disproportionately European) who insisted on a continued commitment to rigorous mathematical formalism were seen as far too persnickety to be worth talking to much. But these last are probably the ones who LtU readers would get on best with. Good names to look for are Lambek, Montague, Kamp, Dowty, Partee, Pollard, Gazdar.

In some areas of linguistics, notably computational linguistics, corpora and data-driven methods came back with the availability of CD-ROM drives on commodity computers, because it was now easy to distribute millions of words of text or speech. It is extremely rare for computational linguistics papers to have any discernible connection to Chomsky's later research, except in the most general and vague terms.