Alonzo Church: The Forgotten Architect of Computer Intelligence

The man who gave us the solution to the Entscheidungsproblem

This is part of a series, of people, who have contributed significantly to their field. Whilst they are known within the field, rarely are they known outside the field or widely, yet should be.

If you've heard of the Turing Test, you've undoubtedly heard of Alan Turing. But in the same breath, you might also encounter the lesser-known name, Alonzo Church. When we review the ‘popular’ history of computing and Artificial Intelligence, it’s often Turing’s name that receives the spotlight, but the collaboration upon which Turing performed much of his groundbreaking work was aided and shaped by Church. Alonzo Church's work profoundly influenced Alan Turing's thinking and played a decisive role in the development of the Turing Test. Furthermore, without Church's contributions to the understanding of computation, our current conceptions of artificial intelligence and the tests, which have considerably evolved, to evaluate it may likely be very different.

Born on June 14, 1903, in Washington, D.C., Alonzo Church was a quiet, soft-spoken logician whose impact on mathematics and computing was monumental, even though he never sought acclaim. Little is known of his early life, however, it was marked by challenges, an air gun incident in his childhood left him blind in one eye[1]. Despite this, he thrived academically. Church finished preparatory school in Connecticut in 1920 and began his university education at Princeton that same year, where he completed his doctoral studies in 1927. After spending time at Harvard and abroad as a National Research Fellow in Göttingen, and Amsterdam, Church returned to Princeton, where he would build much of his academic legacy. Church was known for his exceedingly polite demeanor and meticulous nature. His blackboard writing was immaculate, and he was known to cover important papers in Duco cement to preserve them, a reflection of his careful and deliberate approach to both scholarship and life.

Did you know that despite his immense contributions to computer science, much of Alonzo Church's early life remains relatively unknown? Unlike some of his more famous contemporaries, his personal history hasn't been extensively documented, adding to the air of mystery surrounding this intellectual giant.

Despite his reserved demeanor and personal challenges, Church's intellectual contributions were nothing short of revolutionary.

Church’s most profound contribution was the “λ-calculus,” a formal system that served as the bedrock of computer science before computer science even had a name. In 1936, Alonzo Church formulated what is now known as the Church-Turing thesis, a concept fundamental to theoretical computer science that states any function that can be effectively computed can be computed by a Turing machine or its equivalent. This thesis was groundbreaking, as it provided the framework within which to understand what machines could theoretically do, but also highlighted the boundaries of algorithmic processes. While foundational, the Church-Turing thesis also has limitations and has been subject to debate, particularly concerning the interpretation of 'effective computability' and its implications for physical computation and the nature of human intelligence.

Where Turing proposed his eponymous machine, a model meant to exemplify how mechanical procedures could be translated into logical form, Church provided the pure abstraction that made such a machine theoretically sound. The λ-calculus was almost mystical in its generality and elegance[2]. The influence of λ-calculus can be seen in the very principles of how programs are written today, emphasizing composition, higher-order functions, and immutability. This formalism allowed abstract mathematical problems to be codified and ultimately solved mechanically, and became essential to the architecture of modern compilers and interpreters. His work posed and solved problems about the limits of mathematical procedures, effectively asking: “To what extent can machines replicate human thought?”

In addition to λ-calculus, Church made important contributions to other areas of logic and philosophy, such as his work on the Entscheidungsproblem, a decision problem posed by David Hilbert in 1928 that asked whether there exists a definitive algorithm to determine the truth of any mathematical statement. Church answered this question negatively, showing that such an algorithm does not exist, which became known as Church's Theorem. This finding profoundly influenced decision theory and underscored the limits of what could be achieved with computation alone.

Church was also a mentor to some of the greatest logicians and computer scientists of his time. His academic offspring included luminaries such as Stephen Kleene, J. Barkley Rosser, and perhaps most notably, Alan Turing, who completed his Ph.D. under Church's supervision at Princeton. David Kaplan says that he used always to recommend that his new graduate students sit in on a class with Church, telling them: “Take a class from Professor Church. It will change you. And even if you are not interested in pursuing the subjects he teaches, you will tell your grandchildren.”

During the 1930s, Princeton was an intellectual epicenter for the development of modern logic, with influential figures such as John von Neumann and Kurt Gödel alongside Church. The symmetry of Church's mentorship and Turing's later achievements creates a hidden but potent partnership, an invisible bridge that helped carry humanity from mechanical calculation to computational intelligence.

Did you know that Alonzo Church was already a professor at Princeton University by the age of 26? He joined the faculty in 1929, shortly after completing his Ph.D., showcasing his rapid ascent in academia.

Despite his massive intellectual contributions, Alonzo Church never enjoyed the fame of Turing or von Neumann, Gödel and others. His legacy was one of meticulous abstraction, a kind that doesn’t make it into Hollywood scripts or capture public imagination easily. It lacked the heroism of wartime codebreaking or the evocative tragedy of an early (forced) death. Yet, Church's influence is indelible. The very programs that run on the billions of smartphones today can trace their logic back to the abstract functions of λ-calculus. The invisible DNA of computation, from the simple app to artificial intelligence, owes a significant part of its lineage to Church’s work.

Why, then, should we know him? Perhaps because our reverence for brilliance is often biased toward the visible, the concrete, and the heroic. Alonzo Church’s genius was of a different kind, it was the genius of the unseen, of the rigorous structure without which the edifice could not stand. His work forms a foundational part of the theoretical basis for many of the digital interactions we take for granted, influencing the development of computer science and the algorithmic processes that shape our daily computerised interactions. To know Church is to understand that genius doesn’t always reside in spectacle but sometimes in quiet, unassuming elegance, in the formulas scribbled on a blackboard that, eventually, reshape the world.

With the tremendous breakthroughs we are seeing in artificial intelligence, we would do well to know more about, and celebrate, the foundational figures such as Alonzo Church who made it all possible.

Stay curious,

dr Colin W.P. Lewis

This is part of a series, of people, who have contributed significantly to their field. Whilst they are known within the field, rarely are they known outside the field or widely, yet should be.

Others in the series are Benoît Mandelbrot, Eric Kandel, Hermann Ebbinghaus. Many more to follow.

Recommended reading

Alonzo Church his life, his work and some of his miracles.

On Computable Numbers, with an Application to the Entscheidungsproblem by Alan Turing

Addendum - Read this interesting short reminiscence on Alonzo Church

Note – “Alonzo Church's first published paper, Uniqueness of the Lorentz transformation, appeared in the American mathematical monthly in 1924. His last paper, A theory of the meaning of names, was published in The Heritage of Kazimierz Ajdukiewicz, Rodopi, 1995 (the year he passed away). This amazing span of seventy-two years embraces a remarkable collection of publications on a wide range of topics in logic and in adjacent parts of philosophy, mathematics, and computer science.”

---

[1] (other sources say partially blinded)

[2] To modern programmers, it might look like a set of nested functions, similar to what we see in functional programming languages such as Lisp, Haskell, or even in certain paradigms within Python or JavaScript). Its abstraction provided the groundwork for functional programming, where functions are treated as first-class citizens.