On Tuesday, December 7, 1920, the Göttingen Mathematics Society held its regular weekly meeting—at which a 32-year-old local mathematician named Moses Schönfinkel with no known previous mathematical publications gave a talk entitled “Elemente der Logik” (“Elements of Logic”).
A hundred years later what was presented in that talk still seems in many ways alien and futuristic—and for most people almost irreducibly abstract. But we now realize that that talk gave the first complete formalism for what is probably the single most important idea of this past century: the idea of universal computation.
Sixteen years later would come Turing machines (and lambda calculus). But in 1920 Moses Schönfinkel presented what he called “building blocks of logic”—or what we now call “combinators”—and then proceeded to show that by appropriately combining them one could effectively define any function, or, in modern terms, that they could be used to do universal computation.
Looking back a century it’s remarkable enough that Moses Schönfinkel conceptualized a formal system that could effectively capture the abstract notion of computation. And it’s more remarkable still that he formulated what amounts to the idea of universal computation, and showed that his system achieved it.
But for me the most amazing thing is that not only did he invent the first complete formalism for universal computation, but his formalism is probably in some sense minimal. I’ve personally spent years trying to work out just how simple the structure of systems that support universal computation can be—and for example with Turing machines it took from 1936 until 2007 for us to find the minimal case.
But back in his 1920 talk Moses Schönfinkel—presenting a formalism for universal computation for the very first time—gave something that is probably already in his context minimal.
Moses Schönfinkel described the result of his 1920 talk in an 11-page paper published in 1924 entitled “Über de Bausteine der mathematischen Logik” (“On the Building Blocks of Logic”). The paper is a model of clarity. It starts by saying that in the “axiomatic method” for mathematics it makes sense to try to keep the number of “fundamental notions” as small as possible. It reports that in 1913 Sheffer managed to show that basic logic requires only one connective, that we now call Nand. But then it begins to go further. And already within a couple of paragraphs it’s saying that “We are led to [an] idea, which at first glance certainly appears extremely bold”. But by the end of the introduction it’s reporting, with surprise, the big news: “It seems to me remarkable in the extreme that the goal we have just set can be realized… [and]; as it happens, it can be done by a reduction to three fundamental signs”.
Those “three fundamental signs”, which he actually further reduces to two, are what we now call the S and K combinators (he called them S and C). In concept they’re remarkably simple, but their actual operation is in many ways braintwistingly complex. But there they were—already a century ago—just as they are today: minimal elements for universal computation, somehow conjured up from the mind of Moses Schönfinkel.
So who was this person, who managed so long ago to see so far?
The complete known published output of Moses Schönfinkel consists of just two papers: his 1924 “On the Building Blocks of Logic”, and another, 31-page paper from 1927, coauthored with Paul Bernays, entitled “Zum Entscheidungsproblem der mathematischen Logik” (“On the Decision Problem of Mathematical Logic”).
“On the Building Blocks of Logic”
“On the Decision Problem of Mathematical Logic”
And somehow Schönfinkel has always been in the shadows—appearing at best only as a kind of footnote to a footnote. Turing machines have taken the limelight as models of computation—with combinators, hard to understand as they are, being mentioned at most only in obscure footnotes. And even within the study of combinators—often called “combinatory logic”—even as S and K have remained ubiquitous, Schönfinkel’s invention of them typically garners at most a footnote.
About Schönfinkel as a person, three things are commonly said. First, that he was somehow connected with the mathematician David Hilbert in Göttingen. Second, that he spent time in a psychiatric institution. And third, that he died in poverty in Moscow, probably around 1940 or 1942.
But of course there has to be more to the story. And in recognition of the centenary of Schönfinkel’s announcement of combinators, I decided to try to see what I could find out.