# Proofs are Programs: 19th Century Logic and 21st Century Computing

**Abstract**

As the 19th century drew to a close, logicians formalized an ideal notion of proof. They were driven by nothing other than an abiding interest in truth, and their proofs were as ethereal as the mind of God. Yet within decades these mathematical abstractions were realized by the hand of man, in the digital stored-program computer. How it came to be recognized that proofs and programs are the same thing is a story that spans a century, a chase with as many twists and turns as a thriller. At the end of the story
is a new principle for designing programming languages that will guide computers into the 21st century.
For my money, Gentzen’s natural deduction and Church’s lambda calculus are on a par with Einstein’s relativity and Dirac’s quantum physics for elegance and insight. And the maths are a lot simpler. I want to show you the essence of these ideas. I’ll need a few symbols, but not too many, and I’ll explain as I go along.
To simplify, I’ll present the story as we understand it now, with some asides to fill in the history. First, I’ll introduce Gentzen’s natural deduction, a formalism for proofs. Next, I’ll introduce Church’s lambda calculus, a formalism for programs. Then I’ll explain why proofs and programs are really the same thing, and how simplifying a proof corresponds to executing a program. Finally, I’ll conclude with a look at how these principles are being applied to design a new generation of programming languages, particularly mobile code for the Internet.

**Keywords**

**Categories**

(categorize this paper)

**PhilPapers/Archive ID**

WADPAP

**Revision history**

Archival date: 2015-11-21

View upload history

View upload history

References found in this work BETA

No references found.

Citations of this work BETA

No citations found.

**Added to PP index**

2009-09-12

**Total downloads**

219 ( #10,911 of 35,452 )

**Recent downloads (6 months)**

4 ( #32,126 of 35,452 )

How can I increase my downloads?

**Monthly downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks to external links.*