Category: Computational Science

Happy 100th Birthday, Alan Turing

(This is an updated version of what I wrote for Alan Turing’s 98th birthday.)

Today (June 23, 2012) would have been Alan Turing’s 100th birthday—if he had not died in 1954, at the age of 41.

I never met Alan Turing; he died five years before I was born. But somehow I feel I know him well—not least because many of my own intellectual interests have had an almost eerie parallel with his.

And by a strange coincidence, Mathematica’s “birthday” (June 23, 1988) is aligned with Turing’s—so that today is also the celebration of Mathematica‘s 24th birthday.

I think I first heard about Alan Turing when I was about eleven years old, right around the time I saw my first computer. Through a friend of my parents, I had gotten to know a rather eccentric old classics professor, who, knowing my interest in science, mentioned to me this “bright young chap named Turing” whom he had known during the Second World War.

One of the classics professor’s eccentricities was that whenever the word “ultra” came up in a Latin text, he would repeat it over and over again, and make comments about remembering it. At the time, I didn’t think much of it—though I did remember it. Only years later did I realize that “Ultra” was the codename for the British cryptanalysis effort at Bletchley Park during the war. In a very British way, the classics professor wanted to tell me something about it, without breaking any secrets. And presumably it was at Bletchley Park that he had met Alan Turing.

A few years later, I heard scattered mentions of Alan Turing in various British academic circles. I heard that he had done mysterious but important work in breaking German codes during the war. And I heard it claimed that after the war, he had been killed by British Intelligence. At the time, at least some of the British wartime cryptography effort was still secret, including Turing’s role in it. I wondered why. So I asked around, and started hearing that perhaps Turing had invented codes that were still being used. (In reality, the continued secrecy seems to have been intended to prevent it being known that certain codes had been broken—so other countries would continue to use them.)

I’m not sure where I next encountered Alan Turing. Probably it was when I decided to learn all I could about computer science—and saw all sorts of mentions of “Turing machines”. But I have a distinct memory from around 1979 of going to the library, and finding a little book about Alan Turing written by his mother, Sara Turing.

And gradually I built up quite a picture of Alan Turing and his work. And over the 30+ years that have followed, I have kept on running into Alan Turing, often in unexpected places.
Continue reading

Overcoming Artificial Stupidity

Today marks an important milestone for Wolfram|Alpha, and for computational knowledge in general: for the first time, Wolfram|Alpha is now on average giving complete, successful responses to more than 90% of the queries entered on its website (and with “nearby” interpretations included, the fraction is closer to 95%).

I consider this an impressive achievement—the hard-won result of many years of progressively filling out the knowledge and linguistic capabilities of the system.

The picture below shows how the fraction of successful queries (in green) has increased relative to unsuccessful ones (red) since Wolfram|Alpha was launched in 2009. And from the log scale in the right-hand panel, we can see that there’s been a roughly exponential decrease in the failure rate, with a half-life of around 18 months. It seems to be a kind of Moore’s law for computational knowledge: the net effect of innumerable individual engineering achievements and new ideas is to give exponential improvement.

Wolfram|Alpha query success rate Continue reading

Launching a Democratization of Data Science

It’s a sad but true fact that most data that’s generated or collected—even with considerable effort—never gets any kind of serious analysis. But in a sense that’s not surprising. Because doing data science has always been hard. And even expert data scientists usually have to spend lots of time wrangling code and data to do any particular analysis.

I myself have been using computers to work with data for more than a third of a century. And over that time my tools and methods have gradually evolved. But this week—with the release of Wolfram|Alpha Pro—something dramatic has happened, that will forever change the way I approach data.

The key idea is automation. The concept in Wolfram|Alpha Pro is that I should just be able to take my data in whatever raw form it arrives, and throw it into Wolfram|Alpha Pro. And then Wolfram|Alpha Pro should automatically do a whole bunch of analysis, and then give me a well-organized report about my data. And if my data isn’t too large, this should all happen in a few seconds.

And what’s amazing to me is that it actually works. I’ve got all kinds of data lying around: measurements, business reports, personal analytics, whatever. And I’ve been feeding it into Wolfram|Alpha Pro. And Wolfram|Alpha Pro has been showing me visualizations and coming up with analyses that tell me all kinds of useful things about the data.

Data input Continue reading

Talking about Computing and Philosophy

Wolfram|Alpha, A New Kind of Science, and even Mathematica all have aspects that are philosophy projects. Each of them, in different ways, informs questions in philosophy—and are themselves informed by philosophical ideas and discoveries.

Indeed, the very fact that I decided Wolfram|Alpha might be a possible project was the result of what amounts to a philosophical realization that I learned from A New Kind of Science: there is no bright line that identifies “intelligence”; it is all just computation.

I don’t get to talk much about philosophy. But here is a recording of a keynote speech I was recently asked to give about “computing and philosophy”.

Jeopardy, IBM, and Wolfram|Alpha

About a month before Wolfram|Alpha launched, I was on the phone with a group from IBM, talking about our vision for computable knowledge in Wolfram|Alpha. A few weeks later, the group announced that they were going to use what they had done in natural language processing to try to make a system to compete on Jeopardy.

I thought it was a brilliant way to showcase their work—and IBM’s capabilities in general. And now, a year and a half later, IBM has built an impressive level of anticipation for their upcoming Jeopardy television event. Whatever happens (and IBM’s system certainly should be able to win), one thing is clear: what IBM is doing will have an important effect in changing peoples’ expectations for how they might be able to interact with computers.

When Wolfram|Alpha was launched, people at first kept on referring to it as a “new search engine”—because basically keyword search was the only model they had for how they might find information on a large scale. But IBM’s project gives a terrific example of another model: question answering. And when people internalize this model, they’ll be coming a lot closer to realizing what’s possible with what we’re building in Wolfram|Alpha.

So what really is the relation between Wolfram|Alpha and the IBM Jeopardy project?

IBM Watson and Wolfram|Alpha

Continue reading

Programming with Natural Language Is Actually Going to Work

I love computer languages. In fact, I’ve spent roughly half my life nurturing one particular very rich computer language: Mathematica.

But do we really need computer languages to tell our computers what to do? Why can’t we just use natural human languages, like English, instead?

If you’d asked me a few years ago, I would have said it was hopeless. That perhaps one could make toy examples, but that ultimately natural language just wouldn’t be up to the task of creating useful programs.

But then along came Wolfram|Alpha. In which we’ve been able to make free-form linguistics work vastly better than I ever thought possible.

But still, in Wolfram|Alpha the input is essentially just set up to request knowledge—and Wolfram|Alpha responds by computing and presenting whatever knowledge is requested. But programming is different. It is not about generating static knowledge, but about generating programs that can take a range of inputs, and dynamically perform operations.

So the first question is: how might we represent these programs?

Continue reading

Simple Turing Machines, Universality, Encodings, etc.

(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

The Prize Is Won; The Simplest Universal Turing Machine Is Proved

(This post was originally published on the Wolfram Blog.)

“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 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.

2, 3 Turing machine

Continue reading

Science: Live and in Public

(This post was originally published on the Wolfram Blog.)

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

Today We Put a Prize on a Small Turing Machine

(This post was originally published on the Wolfram Blog.)

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