nlp
The grammar beneath the sentence
It is 1956, and two audiences with nothing else in common need the same theorem. Linguists want to know what kind of machine a human grammar is; the first compiler writers want to know what kind of grammar a machine can parse. Characterize which sentence structures a finite device can recognize — build the hierarchy of grammars and automata, prove the separations between its levels, and locate where natural language sits: beyond the reach of finite-state devices, as the center-embedded sentences suggest. The results must be theorems, not taxonomy. Get it right and both linguistics and programming-language design inherit their mathematical foundations from one construction; get it wrong and the study of language stays a catalogue of examples with no notion of what is possible.
Who this problem belongs to
The two figures whose methods fit it best, out of 57 in contention.
This is Chomsky's own 1956 paper, 'Three Models for the Description of Language,' which introduces the hierarchy of grammars this problem asks for and proves that finite-state (regular) grammars cannot generate the center-embedded, nested dependencies natural language exhibits -- a genuine theorem, not a taxonomy, exactly as the problem demands. His subsequent Syntactic Structures (1957) formalizes context-free and transformational grammars, giving linguistics its first mathematically rigorous foundation and simultaneously giving compiler writers (via context-free grammars) the tool that becomes BNF and every parser generator since. He is answering this problem in the actual year, with the actual theorem, for the actual dual audience it names. Score is not 100 only because the full four-level hierarchy is finalized slightly later with Schutzenberger.
Turing's 1936 universal machine and his hierarchy of computability supply the deepest layer this problem needs: the outer boundary of 'what can a machine recognize at all,' against which finite-state and context-free devices are then shown to be strictly weaker special cases. His work on effective procedures and decidability is the theoretical bedrock the Chomsky hierarchy is built on top of and situated within. The deduction is chronology and specificity: he died in 1954, two years before this problem's 1956 setting, and his own work targets general computability rather than the specific grammar-and-automata hierarchy, the finite-state/context-free separations, and the natural-language application this problem asks to be proven.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
57 figures are scored on this problem. Draw it in a battle to see where you land.