The Most Beautiful Equation
I recently read The Universe in Zero Words: The Story of Mathematics as Told through Equations. It’s a quick read and a good layman’s intro to the history of mathematics, cheerfully challenging the quip that “for every equation you put in your text, you lose half your audience.” The book is about 24 of the most important, beautiful and deep equations in mathematics and physics. Inevitably, of course, classics such as e=mc2 show up, as does Euler’s identity and many others; and just as inevitably, there’s room for discussion. Are some important equations left out? Are these really the most beautiful identities in math? A statistician would want Bayes’ theorem, for instance.
Well, I am not a mathematician. I am, however, a self-taught programmer, and I’m going to try and show you the most beautiful equation in computer science. This will be a more technical post than usual, so if equations scare you, run! Let me know if you liked it or found it too dense, or if you are a mathematician and think I botched your entire discipline.
CS isn’t really a discipline heavy on math equations, indeed one of the major theoretical challenges is how to make a foundation for computer programs that is both practical to program in and possible to reason about mathematically. It is, after all, a hybrid discipline of engineering and mathematics. But there is no doubt in my mind that the following is one of the deepest and most beautiful equations in math. It turns out that there are very deep connections between the foundations of math and the foundations of computing.
Behold, the Y combinator:
It might not look it, but all of computation is contained within this identity! It’s the magic key that enables recursion (see: the end of this post).
A Brief History of Computation
Before modern computers even existed, mathematicians were thinking about them and trying to figure out their properties. 1936 was a very important year in computing, even though not a single digital computer existed yet. That year, two different formal definitions of computation were published, which turned out to be equivalent. The most well-known definition, which is not the one we will concern ourselves with here, is the one provided by Alan Turing. The other definition, which is the one connected to the Y combinator above, was published by Alonzo Church.
Turing’s definition of “numbers that are computable by finite means” is more intuitive, because it relies on an abstract machine that we could imagine being built in reality. Turing’s “universal machine”, which now bears his name–the Turing machine–consists of an infinite tape divided into cells. The cells are filled with symbols. It doesn’t matter whether these symbols are binary or not. Along the tape, a reading head moves one cell at a time. This head can move along the tape, reading and writing to it according to an algorithm. Of course, it was quickly realized that we can put the instructions on the tape itself, which is how modern computers work (both the program and the data it manipulates are inside the computer’s memory).
Turing’s interest in defining “effectively computable” numbers was connected to an old problem called the Entscheidungsproblem, or decision problem. It goes all the way back to the 17th century mathematician Gottfried Leibniz, who constructed a mechanical calculator, and dreamed of finding an algorithm that could determine the truth value of a mathematical proposition. Just prior to 1936, Kurt Gödel had published his ingenious incompleteness theorems, which prove that any mathematical system that is sufficiently powerful to express arithmetic must be either inconsistent or incomplete: either there are statements in the system that are true but unprovable, or it is possible to prove untrue statements (i.e. there are contradictions in the system). But that left the decision problem open: could we build a computer that would determine whether a theorem is provable a given system?
Turing found a way to reduce the Entscheidungsproblem into the following question: can we determine in a finite time whether a given Turing machine will halt or run forever?
Suppose we have a function F(P, Q), called the Haltotron. The Haltotron determines, in a finite time, whether the program P given Q as an input will halt or run forever, and returns the value “true” if it halts and “false” if it doesn’t. Now we can create a paradoxical program, F’, to trip up the Haltotron. It goes as follows:
This reads: if the Haltotron says that F’, given itself as an input, halts, then F’ will run forever. And if the Haltotron says that F’ will run forever, F’ will halt.
This proves that the Haltotron can’t exist. There is no solution to the halting problem, which means there is no solution to the Entscheidungsproblem. It may be true that a program runs forever, but that doesn’t mean we can build a computer to tell us so in finite time.
Church and the Lambda Calculus
Alan Turing is a well-known figure firmly entrenched in popular culture, a war hero who was recently portrayed by Benedict “Sherlock Holmes” Cumberbatch in a major biopic. His contemporary Alonzo Church is virtually unknown outside computer and math circles. Church had actually solved the Entscheidungsproblem shortly before Turing independently published his proof. Although Turing’s paper is full of mathematical equations, the ideas in it can be quite easily explained in layman’s terms. He made up an abstract computer and proved some of its properties. We could conceivably build such a computer (except the tape must be finite, of course). Church’s formalism, on the other hand, is an abstract system called the lambda calculus. Don’t worry, this is not a physical calculus, it’s much simpler. So simple, in fact, that it’s amazing that the definition can compute anything computable by a Turing machine. The hypothesis that a number is computable if and only if it is computable by a Turing machine is called the Church-Turing thesis. This is equivalent to saying it is computable if and only if it can be computed in the lambda calculus.
Turing’s machine is closer to an engineer’s view. A hardware view of computation. Church’s view is based on functions, which is closer to how programmers and mathematicians think about computing. A function relates an input to an output. In the lambda calculus, there are no numbers: the only things that exist are functions from one argument to one result. The trick is that functions can be higher-order: a function can return another function as a result.
Here is a simple lambda term:
This is a function that takes one argument, x, and returns another function which takes another argument y, and then returns the x argument from the enclosing function. Note that functions only take one argument, but it’s trivial to simulate a multi-argument function by returning another function that takes one argument and then uses both arguments. This technique is called currying, named not after the space but after another computer pioneer, Haskell Curry. (There is also a programming language named after him, called Haskell, which is based on the lambda calculus.)
Another thing to note is that functions in the lambda calculus are anonymous: they don’t have any names. It would seem that it’s impossible to compute anything if we aren’t allowed to use loops or recursion. This is where the Y combinator comes in. (The Y combinator is also an anonymous function, we have simply named it as a shorthand–we must substitute it in without using its name to use it.) The Y combinator allows us to define recursive functions without using their names. More on that later.
There is another big problem with computing in the lambda calculus: we don’t have any numbers! How are we supposed to compute anything without numbers? Church found a way to encode numbers as lambda functions, called Church encoding. A Church numeral represents a natural number n as a function that applies itself to a value x n times. The number zero applies the function zero times, the number one applies the function one time, and so on. Here is a table from Wikipedia (I admit I cribbed several images from there):
It’s possible to do math with Church numerals. I won’t show how to do it here, but trust me. Mathematicians know how it’s done.
That leaves recursion, which is at the heart of most complex algorithms. A computer program is a complex operation that jumps back and forth between locations in memory. The factorial function is the product of all integers from 1 to n, so factorial(5) = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 120. We can easily define the factorial function recursively, in terms of itself:
Assuming we know how to multiply numbers in Church encoding, we still can’t define the factorial function, because the definition of factorial refers to itself by name, and functions in the lambda calculus are anonymous. Now we’re getting closer to the Y combinator.
The rules for computing lambda expressions are very simple. The simplest rule captures function application: computing the result of a function given an input. To compute the expression (λx. x) y, we substitute y for all occurrences of x inside the function, to get y. This is called β-reduction (beta).
There is a caveat. Observe what happens when we try to compute a slightly more complicated expression: (λx. (λy.λx. y) x). We substitute x for y to get (λx. ( λx. x)). Did you notice the mistake? The x we were substituting in was supposed to be the argument to the enclosing function, but it turned out to be the argument to the inner function instead.
A lambda term is said to bind its argument, and a variable is said to be free inside a term if it is not bound in it. By naively applying β-reduction, the x that was supposed to be free in λx. y became bound instead. To fix this, we must rename the argument to the inner function, to get λz. x where x is free instead of bound. This is called α-renaming. Functions that are the same form but have been alpha renamed are considered equivalent, but fix the free/bound variable mess: λx. y = λz. y.
The fine folks at Wikipedia have done us the favor of beta reducing this cryptic mess to show us what it does:
This is recursive! Now we can use this to define our factorial function:
This definition uses a function called IsZero that we haven’t defined. You can see its definition on Wikipedia.
You call that one of the most beautiful equations in math?
It may not seem earth-shattering. Church’s model is very abstract and cumbersome. Why not just allow us to name functions? Indeed, all real programming languages allow us to do that, even Haskell. The majority of programming languages aren’t based on the lambda calculus at all.
It might seem neat that we can compute anything using a simple substitution rule, but it seems very disconnected from real computers. Turing’s model at least looks like a computer.
An extremely brief history of computer bugs
This moth is often credited as being the first “computer bug”, found inside the Mark II computer in 1947. But most computer bugs are software bugs. They are inevitable. Even the smartest computer programmers, applying all the best practices of the industry, inevitably introduce bugs when they work with codebases that have tens of thousands of lines of codes, perhaps even millions. It’s impossible for any one person to keep the entirety of such a complex program inside their working memory at the same time. Even if programmers try to break a problem into many small functions that perform a small piece of the solution, bugs happen.
Mathematical objects behave much more predictably than do computers. We can’t reason about a typical computer program in a mathematical fashion. One major source of bugs is trying to apply an operation to a value it is not valid for. For instance, what is the result of “asdfg” + 1? You can’t add a number and a random string like that. Such bugs often crop up in code. That is why programmers have invented type systems: every variable is given a type, and the compiler–the program that translates human-readable code into code that the computer can execute–can check whether an invalid operation is applied to a type before the program is run. This is very useful because many bugs propagate widely: one faulty assumption may not show up until an obscure corner case in an entirely different part of the code. If you tried to compile “asdfg” + 1, the compiler would give you a type error, helpfully pointing out the invalid operation.
Type systems have deep connections to mathematical type theory.
Russell’s paradox and type theory
In the beginning of the 20th century, mathematicians were scrambling to find a consistent foundation for mathematics. This was before Gödel proved that a system with arithmetic could not be both consistent and complete. The basis mathematicians chose to build all the rest of math on was set theory. Bertrand Russell discovered that naive set theory has bugs. Consider the set that contains all sets that don’t contain themselves. If it contains itself, by definition it does not; and if it does, by definition it doesn’t. This proves that such a set cannot exist.
One attempt to fix the bugs in naive set theory was by inventing a theory of types. This is similar to programming language types: certain operations are only valid for certain values. Sets are arranged into a type hierarchy, and can only contain sets lower down in the hierarchy. This way, we avoid sets such as “the set of all sets that don’t contain themselves” or the universal “set of all sets.”
The lambda calculus we’ve looked at here is untyped. By 1940, Church had developed the simply typed lambda calculus. Research in type theory continues. Programming languages such as Haskell are based on typed lambda calculi, but include many practical features that don’t exist in the untyped lambda calculus, such as named functions.
The reason we want to work with such a cumbersome system is, paradoxically, that it’s simple. The simpler the system, the easier it is to reason about mathematically, even if we have to apply some tricks along the way. This translates into safer, more reliable programs for all of us to use. The Y combinator and the wider lambda calculus is a super-abstract mathematical theory with very concrete applications.
The dream scenario would be if we could mathematically prove that a program is correct. As it turns out, there is a direct correspondence between programs and mathematical proofs, called the Curry-Howard isomorphism. It says roughly that a proof is a program, and the formula it proves is its type. It turns out that it is possible to formally verify that a program is correct, and this has been done with real-world programs. However, it’s a whole lot of work and unlikely to be done for most programs.
I can’t believe you’re still with me! To summarize, lambda calculus brings together a number of disciplines: computer science, the theory of mathematical proofs, and the foundations of set theory, on which all modern mathematics is built. Research into these things continues, and the goal is to create better, more reliable programs for all of us to use, as well as to better understand the foundations of mathematics.
See: the beginning of this post, just above “A Brief History of Computation.”
snowghoul
izzy806
prguitarman
discoholicmusic
gummygunk
vaporwave
andulkaphoto
stormborns
kianamaiart
