Not a lot gets written in the general press about foundational issues in mathematics, but this afternoon I found myself talking to a journalist about the subject of certainty in mathematics.

It turned out to be a pretty interesting conversation, so I thought I’d write here about a few things that came up.

Mathematics likes to think of itself as a very certainty-based business. If you’ve “proved something mathematically”, then it’s supposed to just be true. No ifs or buts. Complete certainty.

But in practice that’s not quite how it works—at least the way mathematics has traditionally been done. Because in reality a mathematical proof of the kind people publish in papers is something much more social. It’s a vehicle for convincing other humans—one’s fellow mathematicians—that something is true.

There’ve been a few million mathematical proofs published over the past century or so. Essentially all of them are written in a kind of human-compatible mixture of mathematical formalism and ordinary natural language.

They’re intended for human consumption. For people to read, and process. The best of them aren’t just arguments for some particular theorem. Instead they’re expositions that illuminate some whole mathematical structure.

But inevitably they require effort to read. It’s not just a mechanical matter. Instead, every reader of every proof has to somehow map what the proof is saying into their particular patterns of thought. So that they can personally be convinced that the proof is true.

And of course, in practice, proofs written by humans have bugs. Somewhere between the imprecision of ordinary language, and the difficulty of really thinking through every possible eventuality, it’s almost inevitable that any long proof that’s been published isn’t perfect. And even with an army of people to check it, not every bug will be found.

So how do computers—and Mathematica change this picture?

Continue reading

(This post was originally posted on the NKS Forum.)

The following are some remarks that I made on the Foundations of Math (FOM) mailing list in connection with discussion of the Wolfram 2,3 Turing Machine Prize. Though much of what I say is well understood in the NKS community, I thought it might nevertheless be of interest here.

Several people forwarded me the thread on this mailing list about our 2,3 Turing machine prize.

I’m glad to see that it has stimulated discussion. Perhaps I can make a few general remarks.

What do we learn from simple universal Turing machines?

John McCarthy wrote:

In the 1950s I thought that the smallest possible (symbol-state product) universal Turing machine would tell something about the nature of computation. Unfortunately, it didn’t.

I suspect that what was imagined at that time was that by finding the smallest universal machines one would discover some “spark of computation”—some critical ingredient in the rules necessary to make universal computation possible. (At the time, it probably also still seemed that there might be a “spark of life” or a “spark of intelligence” that could be found in systems.)

I remember that when I first heard about universality in the Game of Life in the early 1970s, I didn’t think it particularly significant; it seemed like just a clever hack.

But a few decades later—after building up the whole framework in A New Kind of Science, I have a quite different view. Continue reading

(Main prize page: The Wolfram 2,3 Turing Machine Research Prize)

“And although it will no doubt be very difficult to prove, it seems likely that this Turing machine will in the end turn out to be universal.”

So I wrote on page 709 of A New Kind of Science (NKS).

I had searched the computational universe for the simplest possible universal Turing machine. And I had found a candidate—that my intuition told me was likely to be universal. But I was not sure.

And so as part of commemorating the fifth anniversary of A New Kind of Science on May 14 this year, we announced a $25,000 prize for determining whether or not that Turing machine is in fact universal.

I had no idea how long it would take before the prize was won. A month? A year? A decade? A century? Perhaps the question was even formally undecidable (say from the usual axioms of mathematics).

But today I am thrilled to be able to announce that after only five months the prize is won—and we have the answer: the Turing machine is in fact universal!

Alex Smith—a 20-year-old undergraduate from Birmingham, UK—has produced a 40-page proof.

I’m pleased that my intuition was correct. But more importantly, we now have another piece of evidence for the very general Principle of Computational Equivalence (PCE) that I introduced in A New Kind of Science.

We are also at the end of a quest that has spanned more than half a century to find the very simplest universal Turing machine.

Here it is. Just two states and three colors. And able to do any computation that can be done.

Continue reading

I don’t have much time for hobbies these days, but occasionally I get to indulge a bit. A few days ago I did a videoconference talking about one of my favorite hobbies: hunting for the fundamental laws of physics.

Physics was my first field (in fact, I became a card-carrying physicist when I was a teenager). And as it happens, the talk I just gave (for the European Network on Random Geometry) was organized by one of my old physics collaborators.

Physicists often like to think that they’re dealing with the most fundamental kinds of questions in science. But actually, what I realized back in 1981 or so is that there’s a whole layer underneath.

There’s not just our own physical universe to think about, but the whole universe of possible universes.

If one’s going to do theoretical science, one had better be dealing with some kind of definite rules. But the question is: what rules?

Nowadays we have a great way to parametrize possible rules: as possible computer programs. And I’ve built a whole science out of studying the universe of possible programs—and have discovered that even very simple ones can generate all sorts of rich and complex behavior.

Well, that’s turned out to be relevant in modeling all sorts of systems in the physical and biological and social sciences, and in discovering interesting technology, and so on.

But here’s my big hobby question: what about our physical universe? Could it be operating according to one of these simple rules? Continue reading

When I hear about something like Wednesday’s bridge collapse, I immediately wonder whether any of the science I’ve worked on can be of any help.

Bridge design is one of the classic—almost iconic—successes of traditional mathematical science.

And when I first talked about A New Kind of Science, a not uncommon reaction was precisely, “But can it help build better bridges?”

Well, as a matter of fact, I rather suspect it can.

Bridges have a long history. Early on, only a few types seem to have been used. But with the arrival of iron structures in the 1800s there was a kind of “Cambrian explosion” of different types of truss bridges:

But what is the very best bridge structure, say from the point of view of robustness? There’s a huge universe of possibilities. But so far, only a tiny corner has been explored—and that mostly in the 1800s. Continue reading

Our 2007 NKS Summer School started about two weeks ago, and one of my roles there was to show a little of how NKS is done.

In the past, it would have been pretty unrealistic to show this in any kind of live way. But with computer experiments, and especially with Mathematica, that’s changed. And now it’s actually possible to make real discoveries in real time in front of live audiences.

I’ve done a few dozen “live experiments” now (here is an account of one from 2005). My scheme is as follows. Sometime between a few hours and a few minutes before the live experiment, I come up with a topic that I’m pretty sure hasn’t been studied before. Then I make sure to avoid thinking about it until I’m actually in front of the live audience.

Then, once the experiment starts, I have a limited time to discover something. Just by running Mathematica. Preferably with a little help from the audience. And occasionally with a little help from references on the web.

Every live experiment is an adventure. And it seems like almost every time, at around the halfway point, things look bad. We’ve tried lots of things. We’ve opened lots of threads. But nothing’s coming together.

But then, somehow, things almost always manage to come together. And we manage to discover something. That’s often pretty interesting. (There are still papers coming out now based on the live experiment I did at our very first Summer School, back in 2003).

I usually make my first live experiment at each Summer School be a piece of “pure NKS”: an abstract investigation of some simple program out in the computational universe.

This year I decided to take a look at an “old chestnut” that I’d recently been reminded about: a simple program (though it wasn’t thought of that way then) that was actually first investigated all the way back in 1920. Continue reading

It is perhaps ironic that two weeks after releasing what is probably the single most complex computational system ever constructed, we are today announcing a prize for the very simplest of computational systems.

But today is the fifth anniversary of the publication of A New Kind of Science, and to commemorate this, we have decided to establish the first NKS prize.

The prize is related to a core objective of the basic science of NKS: to map out the abstract universe of possible computational systems.

We know from NKS that very simple programs can show immensely complex behavior. And in the NKS book I formulated the Principle of Computational Equivalence that gives an explanation for this discovery.

That principle has many predictions. And one of them is that the ability to do general-purpose computing—to be capable of universal computation—should be common even among systems with very simple rules.

Today’s CPUs have millions of components. But the Principle of Computational Equivalence implies that all kinds of vastly simpler systems should also support universal computation.

The NKS book already gives several dramatic examples. But the purpose of the prize is to determine the boundary of universal computation for a particularly classic type of computational system: Turing machines. Continue reading

New technology is often what has driven the creation of new science. And so it has been with Mathematica.

One of the main reasons I originally started building Mathematica was that I wanted to use it myself.

And having Mathematica was a bit like having one of the first telescopes: I could point it somewhere, and immediately see all sorts of new things that had never been seen before.

Much has been discovered with Mathematica in almost every area of science.

But my particular interest has been to create a new kind of science that is uniquely made possible by Mathematica: a science based on exploring the computational universe.

We are used to creating computer programs for particular purposes. But as a matter of basic science we can ask about the universe of all possible programs.

And with Mathematica it becomes easy to explore this.

A quarter of a century ago I had begun my exploration of the computational universe—and had glimpsed some remarkable phenomena.

Then, when Mathematica was built, I went back and started a systematic study of the computational universe.

The results were remarkable. Wherever I looked—even among the simplest of programs—I saw all sorts of complex and interesting behavior. And from what I found I could make progress on a remarkable range of longstanding questions across all sorts of areas.

For eleven years I worked to develop this. And finally, on May 14, 2002, I published what I had done in my book A New Kind of Science.

Today is the fifth anniversary of that event. Continue reading

Mathematica 1.0 was released on June 23, 1988—now nearly 19 years ago. And normally, after 19 years, pretty much all one expects from software products is slow growth and incremental updates.

But as in so many things, Mathematica today just became a big exception.

Some people have said that Mathematica 6.0 shouldn’t even be called “Mathematica” at all. That it’s something so qualitatively new and different that it should be given a completely different name.

Well, perhaps I’m just too sentimental. Or too steeped in history. Or too naive about branding. But to me there’s no choice. We owe it to all the foundations we’ve laid these past twenty years to still call what we’ve built today “Mathematica.”

Realistically, I think it took us ten years after Mathematica 1.0 just to realize what a powerful thing we had in Mathematica.

We’d always talked about “symbolic programming,” and how it let us unify a lot of different ideas and areas. But sometime around the mid-1990s it began to dawn on us just what an amazing thing symbolic programming actually is.

And we began to think that there might be a whole new level one could reach in computing if one really did everything one could with symbolic programming.

Well, that was an intellectual challenge we couldn’t resist. So about ten years ago, we embarked on seeing just what might be possible. Continue reading

(This post was originally published on the NKS Forum.)

Last Friday (April 28, 2006) would have been Kurt Gödel’s 100th birthday. I agreed to try to write something about it for publication in a newspaper … which had the dual misfeatures that (a) I had to compress what I was saying and (b) that it didn’t actually get done…

Still, I thought people on the Forum might find my draft interesting … so here it is. Please recognize that this wasn’t polished for final publication…

When Kurt Gödel was born—one hundred years ago today—the field of mathematics seemed almost complete. Two millennia of development had just been codified into a few axioms, from which it seemed one should be able almost mechanically to prove or disprove anything in mathematics—and, perhaps with some extension, in physics too.

Twenty-five years later things were proceeding apace, when at the end of a small academic conference, a quiet but ambitious fresh PhD involved with the Vienna Circle ventured that he had proved a theorem that this whole program must ultimately fail.

In the seventy-five years since then, what became known as Gödel’s theorem has been ascribed almost mystical significance, sowed the seeds for the computer revolution, and meanwhile been practically ignored by working mathematicians—and viewed as irrelevant for broader science.

The ideas behind Gödel’s theorem have, however, yet to run their course. And in fact I believe that today we are poised for a dramatic shift in science and technology for which its principles will be remarkably central.

Gödel’s original work was quite abstruse. He took the axioms of logic and arithmetic, and asked a seemingly paradoxical question: can one prove the statement “this statement is unprovable”? Continue reading