The History and Future of Special Functions

Given at the Wolfram Technology Conference 2005 in Champaign, IL as part of the Festschrift for Oleg Marichev, in honor of his 60th birthday.

OK, well now I want to turn to my main talk for this morning. I'm going to talk about the history and future of special functions. I've actually been a special-functions enthusiast for more than 30 years. And I think I've probably been indirectly responsible for promoting more special-functionism in the world than pretty much anyone else. But I realize that I've actually never given any kind of talk about special functions before. So here goes.

Well, like so many things in mathematics, one can trace the story back to ancient Babylon. Where already four thousand years ago there was all sorts of elaborate base-60 arithmetic being done.

In those days addition and subtraction seem to have been considered quite straightforward. But multiplication and division weren't. And what got invented to do them was in essence a version of special functions.

What happened was that division got reduced to adding and subtracting reciprocals. And multiplication—rather ingeniously—got reduced to adding and subtracting squares.

So in effect all sorts of different computations were organized so that the core of them was just table lookup. And sure enough we find Babylonian clay tablets with tables of reciprocals and squares.

So in effect the Babylonians already had the key idea that there exist fairly small nuggets of mathematical or computational work that one can use over and over again to build up lots of useful things.

And in a sense the history of special functions is a history of the discovery of a sequence of useful such "nuggets."

Well, the next nuggets were probably ones involving trigonometry. The Egyptian Rhind papyrus from 1650 BC already has problems about pyramids that need trigonometry. And there's a Babylonian tablet that's been found with a table of secants on it.

Astronomers—with their epicycle-type models—definitely seem to have been serious users of trigonometry. And again they seem to have reduced things to a small number of definite "special" functions.

They particularly wanted to know what they called "chords" and "arcs." Here's the picture.

Enlarge Image

Given a certain angle at the center of a circle, what's the length of the chord it gives? Which is of course what we now call the sine function.

And then the inverse: given the length of the chord, what's the length of the arc that goes with? Which, surprisingly enough, is what we now call the arc sine function.

Well, the Greek astronomers were pretty serious about their chords and arcs. Ptolemy's Almagest is full of them. And around 140 BC it's said that Hipparchus compiled 12 books of chord tables.

Well, from Babylon and Greece, the idea of trigonometry diffused out. Lots of standards got set quite early. Hipparchus had already got from the Babylonians the idea of having 360 degrees in a circle.

And from the Indian word for "chord," literally transliterated into Arabic, and then mistranslated into Latin, the word "sine" had emerged by the 1100s, and was used by Fibonacci by the beginning of the 1200s.

By the 1300s, trigonometry was getting pretty well established. And in the mid-1500s, it was pretty crucial to Copernicus's big book De Revolutionibus. Which, starting a long-continued tradition, effectively had an appendix about mathematical functions.

Lots of the trigonometry there is just like today. There are a few noticeable differences, though. Like a lot of use of the versine. Anyone know what that is? It's actually 1-Cos[x]—a sine "versed" through 90 degrees. And you'll find it in books of tables up to quite recently. But today it's so easy to do the extra arithmetic that it's not worth talking about this function.

Well, after trigonometry, the next big thing was logarithms. Which burst onto the scene in 1614.

Enlarge Image

As a way to reduce multiplications and divisions to additions and subtractions.

Within a few years, there were many tables of logarithms. It had become quite an industry—which actually lasted more than 300 years.

It took a few years for natural logarithms and exponentials to get their modern form. But then by the mid-1600s all of the ordinary elementary functions were firmly in place. And from then until now they've been essentially the only explicit mathematical functions that most people ever learn about.

Well, in the late 1600s calculus arrived. And that's when today's special functions started appearing. Most of it actually happened rather quickly.

Around 1700 one of the Bernoullis had the idea that perhaps the integral of any elementary function would be an elementary function. Leibniz thought he had a counterexample with 1/(x^4+a^4). But that didn't pan out. Still, within a couple of years people were talking about elliptic integrals. At least in terms of series. And they'd seen Bessel functions.

And by the 1720s, Euler was starting his major industrial drive into the world of calculus. And he started talking about lots of our standard special functions.

He found the gamma function as a continuation of factorial. He defined Bessel functions for investigating circular drums. He looked systematically at elliptic integrals. He introduced the zeta function. He looked at polylogs.

He usually didn't give the functions explicit names.

But gradually more and more of the functions he talked about started being used by several people. And usually after a few iterations they started having definite notations, and definite names.

There were a few more bursts of special-function activity. In the late 1700s, there was potential theory and celestial mechanics. And for example Legendre functions—also for a long time called Laplace functions—came in around 1780. Then in the 1820s, complex analysis was all the rage, and the various doubly periodic functions came in. There wasn't terribly good communication between people in the field. So there ended up being quite a few incompatible notations. Which have persisted to the present day, and regularly lead to Mathematica tech support calls.

A few years later, harmonic analysis got big, and the various orthogonal polynomials—Hermite, Laguerre, and so on—came in.

Well, even quite early in the 1800s, it was already fairly clear that a serious zoo of special functions was developing. And that got Gauss in particular thinking about how to unify it.

He investigated hypergeometric series—which had in fact already been defined and named by Wallis in the 1650s. And he noted that the 2F1 or Gauss hypergeometric function actually covered a lot of known special functions.

Well, by the mid-1800s there was a serious industry of scholarship about special functions—particularly in Germany—with many erudite books being written. So by the time Maxwell was writing his books on electromagnetic theory in the 1870s he didn't think he even needed to say much in his books about special functions; he just quoted standard books.

Along with scholarly works listing properties of functions, there were also tables of values being created. Sometimes by people one's never heard of. And sometimes by people one has—like Jacobi or Airy or Maxwell.

So, well before the end of the 1800s, essentially all the special functions we deal with today were established. There were some extras too. Like does anyone know what a Gudermannian is? I remember seeing it in books of tables when I was a kid. It's named after Christof Gudermann, a student of Gauss's. And it gives a relation between ordinary trig functions and hyperbolic functions. And it's also relevant to Mercator projections of maps. But somehow it hasn't really made it to modern times.

Well, there was lots of erudition poured into special functions in the last few decades of the 1800s. And I suppose they could have gone the way of invariant theory, or syzygies, or those other somehow characteristically Victorian mathematical pursuits. And indeed in most of pure mathematics, the push towards abstract generality made special functions look rather irrelevant and arbitrary. Like studying strange specific animals in a zoo, rather than looking at general biochemistry.

But physics kept on reenergizing special functions. Mechanics. Elasticity theory. Electromagnetic theory. Then in the 1920s quantum mechanics, where even the most basic problems involved special functions—like Laguerre polynomials and Hermite polynomials. And then there was scattering theory, which seemed to use almost the whole zoo of special functions.

Well, one of the things that happened from all this was that people got the idea that any nice clean problem could somehow always be solved in terms of special functions. And certainly the textbooks encouraged that idea. Because the problems they discussed were somehow always ones that came out nicely in terms of special functions.

There were cracks, to be sure. Quintic equations. The three-body problem. But these were somehow thought to be unusually messy. Not really the norm. And not what one needed to look at in modern probabilistic theories.

But special functions were a big business. Table making had become a major government activity—particularly in England. And was thought strategically important. Particularly for things like navigation. And there were lots of tables. Like here's a particularly fine set from 1794. When I first saw them, I thought it was a time warp.


Enlarge Image

(Actually, that Wolfram was a Belgian artillery officer. Probably no more of a relation than the Saint Wolfram in the 7th century AD.) Tables were sufficiently important that Babbage had for example come up with his difference engine in the 1820s specifically for the purpose of printing accurate tables. And by the late 1800s, special functions were a common subject of tables that were being made.

Mechanical calculators were becoming ever more widespread, and in Britain and the U.S. there were huge special-function-table projects. Like the WPA project in the 1930s—to give people jobs during the Depression computing mathematical functions.

There were gradually starting to be systematic reference works on the properties of special functions. Each one was a lot of work, so there really weren't very many. Though they thought they were pretty important. Like here's the cover of the U.S. edition of Jahnke and Emde, first published in the 1909 and, by the 1930s, with pictures added.

Enlarge Image

They were lovely pictures, by the way.

Enlarge Image

Emulating the plaster and wood models of functions that arrived in so many math departments in the early 1900s. And in fact, I got the idea for the picture of the zeta function that I used on the first edition of The Mathematica Book from Jahnke and Emde.

Enlarge Image

Somehow a lot of special-function reference work came to a head right at the time of the Second World War. I'd sort of assumed it was for military reasons. But actually I think it was a coincidence. But the potential connection with strategic stuff made it not get closed down.

And so the first edition of Magnus and Oberhettinger was published in 1943.

Enlarge Image

As was the first edition of what became Gradshteyn-Ryzhik.

In 1946, Harry Bateman died, having collected a dozen shoeboxes of cards with facts about special functions. Which eventually got published as the Bateman Manuscript Project.

The Manhattan project, and later the H-bomb development project, were important consumers of special functions. And in 1951, for example, Milt Abramowitz at the National Bureau of Standards made Tables of Coulomb Wave Functions, needed for nuclear physics.

Enlarge Image

And from this gradually grew the Abramowitz-Stegun book published in 1965, which became the staple for American special-function users.

Enlarge Image

In the 1960s and 70s there was beginning to be lots of effort put into numerical algorithms for computers. And special-function evaluation was a favorite area.

The work was in most cases painfully specific—with huge amounts of time being spent on a particular Bessel function of a particular order to a particular precision. But there gradually emerged subroutine libraries with collections of specific special-function-evaluation algorithms. Though really most people still used books of tables, which were to be found in prominent places in the reference sections of science libraries.

Well, my own involvement with special functions started when I was a mid-teenager, in the mid-1970s. The official math that I learned in school in England pointedly avoided special functions. It tended to be all about finding clever tricks to squeak through to an answer just using elementary functions. I wasn't very happy with that. I wanted something more systematic, more technological. Less tricky. And I liked the idea of special functions. They seemed like bigger hammers to hit problems with. Though the discussion of them in mathematical physics books never seemed terribly systematic. Yes, they were more-powerful functions. But they still seemed quite arbitrary—a kind of zoo of curious creatures with impressive-sounding names.

I think I was 16 when I first actually used a special function for real. It was a dilogarithm. And it was in a particle physics paper. And I'm embarrassed to say that I just called it f.

Enlarge Image

But my excuse is that polylogarithms were actually pretty unknown then. The standard mathematical physics books had Bessels and elliptic integrals and orthogonal polynomials, even some hypergeometric functions. But no polylogarithms. As it turns out, Leibniz had already talked about dilogarithms. But somehow they hadn't made it in the usual historical zoo of special functions. And the only real information about them that I could find in the mid-1970s was a book from 1959 by a microwave engineer named Leonard Lewin.

Soon thereafter, I started computing lots of integrals for Feynman diagrams. And I realized that there polylogarithms were really absolutely the key functions that were needed. They became my friends, and I started collecting lots of properties of them.

Enlarge Image

And there was something that I noticed then, that I didn't really realize the significance of until much later. I should explain that in those days doing integrals well was sort of a hallmark of a good theoretical physicist.

Well, I had never thought of myself as algebraically talented. But somehow I discovered that by using fancy special functions, I could do integrals like the best of them. Lots of people even started coming to me to do integrals. Which I found kind of amazing. Especially since it seemed like every integral I did, I did just by writing it as a parametric derivative of a beta function integral.

And I think from this I had some dim awareness that the way to do lots of integrals might be by going to higher functions, and then back again. A bit like one has to go to complex numbers to solve real cubics. And lots of other things like that in math.

Well, by 1978 or so, I decided I really needed to codify how to do these integrals. And here for example was a block diagram of a Macsyma program that I made for it.

Enlarge Image

A combination of algorithms and table lookup. That actually did work, and was quite useful.

Enlarge Image

Well, in addition to polylogs, I kept on running into other special functions. K-type Bessel functions in cosmology calculations.

Enlarge Image

QCD calculations that became a whole festival of zeta functions. I made a theory of "event shapes"—that still gets used in many particle physics experiments today—that was completely based on spherical harmonics and Legendre polynomials.

I was thrilled one day when my theory of jet development in QCD gave me I-type Bessel functions. I'd never met those in the wild before.

You know, the culture around special functions was interesting. It was always very satisfying when a problem came out in terms of a special function. It was sort of stylish.

It was sort of funny showing particularly an older physicist some mathematical problem. They'd look at it a bit like an archaeologist looks at a pot shard. They'd stroke their beard if they had one. And opine that, yes, that might be a Laguerre polynomial.

And when someone said that their problem involved a special function, it was as if it contained some exotic spices brought in from the East. Well, actually, the East was involved. Because somehow, at least in the U.S. in the late 1970s, special functions seemed to have a particularly Russian flavor to them.

At least among physicists, the Abramowitz-Stegun book was fairly well known. Jahnke and Emde was essentially unknown. As was Magnus and Oberhettinger, and so on. And I think only mathematicians ever talked about the Bateman Manuscript Project. (Even at Caltech, where it had been done.) But somehow "physicists in the know" used Russian materials, and particularly Gradshteyn-Ryzhik.

I was never very clear just how special functions got such a Russian connection. People used to say that it was because the Russians did not have very good computers, so they had to do every possible thing analytically. I'm not sure that's really what was going on.

And actually, in thinking about this talk I decided it was time finally to find out the story behind Gradshteyn-Ryzhik.

Enlarge Image

I still don't know the full story. But here's what I know.... In 1936 Iosif Moiseevich Ryzhik had a book entitled Special Functions published by the United Moscow-Leningrad Scientific-Technical Publisher. Ryzhik died in 1941, either during the siege of Leningrad, or fighting on the Russian front. In 1943, a table of formulas was published under Ryzhik's name by the Governmental Moscow-Leningrad Technical-Theoretical Publisher. The only thing the book seems to say about its origins is that it's responding to the shortage of books of formulas. It says that some integrals marked in it are original, but the others mostly come from three books—a French one from 1858, a German one from 1894, and an American one from 1922. It explains that effort went into the ordering of the integrals, and that some are simplified by using a new special function s equal to Gamma[x+y-1]/(Gamma[x]Gamma[y]). It then thanks three fairly prominent mathematicians from Moscow University. That's basically all we know about Ryzhik. It's more than we know about Euclid—but not much.

OK, so now for the next part of the story. Israil Solomonovitch Gradshteyn was born in 1899 in Odessa, and became a professor of mathematics at Moscow State University. But in 1948, he was fired as part of the Soviet attack on Jewish academics. To make money, he wanted to write a book. And so he decided to build on Ryzhik's tables. Apparently he never met Ryzhik. But he created a new edition, and by the third edition, the book was known as Gradshteyn-Ryzhik.

Gradshteyn died of natural causes in Moscow in 1958. Though somehow there developed an urban legend that one of the authors of Gradshteyn-Ryzhik had been shot as a piece of anti-Semitism on the grounds that an error in their tables had caused an airplane crash.

Meanwhile, starting around 1953, Yurii Geronimus, who had met Gradshteyn at Moscow State University, began helping with the editing of the tables, and actually added the appendices on special functions. Later on, several more people were involved. And when the tables were published in the West, there were arguments about royalties. But Geronimus is now still alive and well and living in Jerusalem, and Oleg phoned him last week.

I guess integrals are timeless. They don't really bear the marks of the human creators. So we have the tables, but we really don't quite know where they came from.

Well, OK, so in the late 1970s I had become a fairly serious special-functions enthusiast. So in 1979, when I started building SMP, which was in some ways a precursor to Mathematica, it was only natural for it to have good coverage of special functions. It just seemed like that was clearly a part of doing mathematics by computer.

Well, here is a very early design document for SMP, written in the first couple of weeks of the project. And already with evidence of special functions.

Enlarge Image

Here's a slightly later one.

Enlarge Image

And by the time SMP Version 1 was released in 1981, it had a pretty complete list of special functions.

Enlarge Image

The support for some of them was quite thin. But people were already quite excited to see their favorite functions in there. The numerics for the functions were somewhat primitive. But one thing that helped a lot was that we spent a lot of effort on the evaluation of fairly general hypergeometric functions. And then we treated many other functions as special cases. Which was OK, except for the fact that quite often the most interesting cases of functions end up being sort of degenerate limits. So in practice even the numerics ended up being a bit spotty.

Well, a few years passed. And in 1986 I started designing Mathematica. And this time, I wanted to be sure to do a definitive job, and have good numerics for all functions, for all values of parameters, anywhere in the complex plane, to any precision.

At first I thought perhaps I should try talking to experts. And I remember very distinctly a phone call I had with someone at a government lab. I explained what I wanted to do. And there was a silence. And then he said: "Look, you have to understand that by the end of the 1990s we hope to have the integer-order Bessel functions done to quad precision."

OK, so we needed another approach. See, the problem was that the guy with the Bessel functions was thinking that he was going to be the one deriving all the numerical methods. But what I realized was that to do what we wanted to do, we needed automation. And what happened is that Jerry Keiper developed a whole automated system for searching for algorithms for function evaluation. It's in some ways a very NKSish thing: we set up general forms of rational approximations to functions. Then we just did big searches to optimize the parameters.

And it worked really well. And it let us grind through getting good numerics for all our functions.

You know, it's actually quite a difficult thing to put a special function into Mathematica. You don't just have to do the numerics. For all parameter values and so on. But you also have to support all sorts of symbolic properties. Like derivatives, and series, and asymptotic expansions. With respect to arguments, and parameters. And everything. Often we have to derive completely new formulas. That have never been in the literature.

And of course we have to hook the functions into integrals, and differential equations, and sums, and integral transforms. And FunctionExpand, and FullSimplify. And everything. There's a long list.

Often the very trickiest issues come because of branch cuts. Most continuous special functions are in effect defined implicitly, usually from differential equations. And that means that—just like with something like a square root—they can in general have multiple possible values. Corresponding to different sheets on their Riemann surface.

Well, to make genuine functions out of them one has to pick a principal sheet. And that means there end up being seams—or branch cuts—where there are discontinuities. And representing those branch cuts symbolically is a really really tricky business. Even for elementary functions. Like here's the official, branch-cut-correct version of the standard formula that Sin[x] == Sqrt[1 - Cos[x]^2].

Enlarge Image

They don't teach that in school. And actually we only derived it fairly recently. But it's what you need if you want to get symbolic manipulations with these functions in the complex plane correct.

Well, OK, we've put a lot of effort into special functions in Mathematica. With algorithms. Formulas. And now our whole Wolfram Functions Site. And by immense amounts of human effort—and clever automation—we've multiplied by a large factor the special function knowledge that's in the world.

I think it's ended up having quite a bit of an effect. It's hard to measure, but somehow I think having all these functions as accessible as sine and cosine has made them vastly more popular. They are no longer obscure things nobody's ever seen. They're things anyone might get out of The Integrator. Not just conserved like an endangered mathematical species. But developed and made mainstream and useful.

Well, OK, I said I would say something about the future of special functions. It's interesting to see special-function trends. There are lots of special functions that are always in style. Like the Bessels. Or the orthogonal polynomials. Then there are things like polylogs, that languished for a long time, but ended up coming to prominence fairly recently through several quite separate applications. There are special functions that are still languishing. Like the Painlevé transcendents. From a hundred years ago. That people occasionally ask about in Mathematica.

Well, in developing Mathematica, we regularly talk about the future of special functions. Which functions will really be useful for the kinds of directions people seem to be taking. Which ones are a huge amount of effort to support, but will go the way of the Gudermannian.

One obvious current trend—that recent Mathematicas have obviously been part of—is getting functions from discrete difference equations as well as continuous differential equations. From RSolve and Sum instead of DSolve and Integrate. Of course, like so many ideas, this one isn't really new. George Boole was already very modern in 1859 and 1860, when he published two parallel books: A Treatise on Differential Equations and A Treatise on the Calculus of Finite Differences. And in Mathematica 5 we exhumed a lot of his results—and, as it happens, Babbage's—and made algorithms out of them.

Well, for Boole and Babbage, it didn't really count as a "solution" if it didn't come out in terms of elementary functions. But one can perfectly well have discrete special functions—and I wouldn't be surprised that if we invent them correctly, we'll find they were already seen in the 1600s.

Well, OK, thinking about all this makes one really want a more general theory of special functions. Some kind of more fundamental framework.

The qualitative picture—ever since the Babylonians—is that special functions are sort of organizing centers for mathematical calculations. In the sea of possible functions, they're definite anchor points. Functions with fairly few arguments, that somehow can be used as primitives in a lot of useful calculations.

In a sense, it's a little like built-in functions in the Mathematica language. There's a sea of possible computations people want to do. And our job in designing Mathematica is to find certain good primitives—that we can name and implement—from which those computations can be built up.

So what makes a special function good? Well, we can start thinking about that question empirically. Asking what's true about the special functions we normally use. And of course, from what we have in Mathematica and in our Wolfram Functions Site, we should be in the best position in the world to answer this.

Well, here are a few facts. First, most special functions have a small number of arguments. Two is the most common. In old-fashioned printed tables there was a big deal about "single entry" tables—functions with one argument. "Double entry" tables were possible. And beyond that they became very awkward.

Well, of course we don't have exactly the same constraints now. But as the number of arguments goes up, there are sort of more nooks and crannies for a function. It's harder to support it well, and one somehow loses the integrity of talking about something as being a particular special function.

Here's another thing one can ask: how connected is a particular special function? How many relations does it have? To itself? To other functions? Well, one can answer this rather quantitatively from the Wolfram Functions Site. Here's the complete sparse matrix of what function in the Wolfram Functions Site refers to what other function.

Enlarge Image

And here's a table of the most referred-to functions by Google-style page rank.

Enlarge Image

And here's a picture of the top four links from each function.

Enlarge Image

One might have thought that the more relations a function has, the more useful it would be. But the Gamma function—which is one of the most useful special functions—has very few relations. Whereas the Weierstrass functions—which aren't so useful—have oodles of relations. And Zeta is like a very separate prize peacock.

OK, but let's look a bit more carefully at the continuous special functions that we typically use. Ever since the beginning of calculus, power series have been one of the main ways one looks at functions. And indeed essentially all the special functions that we use have a rather special feature in their power series: the coefficients are rational. So that the coefficient of z^n is some rational function of n. And that means that the functions are hypergeometric. They can be expressed in terms of pFq generalized hypergeometric functions.

And at least to some extent the values of p and q for a particular function are correlated with how exotic the function is. Power is a {0,0}. The trigs and inverse trigs are {1,0}'s. Erf is a {1,1}. BesselJ is a {0,1}. EllipticK is a {2,1}. And the 6-j symbol is a {4,3}. There are a few functions that we use that aren't hypergeometric. Like the Mathieu functions, for example.

But so maybe this is our answer: that for some reason what we mostly need are things with rational power series, and the special functions are ways to package those things. But there's an easy experiment that shows that that's not the whole story.

We can just enumerate possible rational power series, and ask what functions they are. It's an easy thing to do with Sum in Mathematica. Here are some results:

Enlarge Image

Now of course everything is some kind of pFq hypergeometric function. But what's notable is how rarely friendly functions like Gamma or Bessels show up. It's mostly raw pFq's.

So there's clearly some other selection process going on to get to the common special functions.

Well, one important characteristic of a hypergeometric function is that it satisfies a differential equation. So here's another theory: perhaps the special functions that occur are just solutions to a certain class of differential equations.

And that's definitely much closer. Let's just imagine enumerating second-order differential equations constructing integer polynomials, say from digit sequences of successive integers. Then using DSolve on them. Well, here's the result.

Enlarge Image

It's kind of interesting. From just this one class of differential equations, we're seeing lots of our favorite special functions. So this is definitely part of the answer.

But again this isn't the whole story. Take a look at the whole array of results from DSolve. There are holes. Are the holes just deficiencies in DSolve? No, not most of the time. Most of the time they're "missing" special functions.

It's actually rather easy to set up equations that need these. Even integrals can do it. Like the integrals of Sin[Sin[x]]. You might think that'd have to be a fairly straightforward special function. And indeed lots of that kind of nested trig integral are. But this isn't. To express it as a special function, you'd have to go to much more complicated two-variable hypergeometric functions.

It's kind of fun these days. Integrate in Mathematica is good enough that one can use it to get a fairly accurate map with it. Just trying out different integrals, and seeing where the boundaries of being able to do them with special functions are.

And here's sort of a very fundamental issue: just what kinds of computations can one expect to give "exact solutions" in terms of special functions? In theoretical physics, there's tended to be a sort of implicit view that for anything that's worthy of being called a physics problem, it should be possible with enough effort to "solve" it. QCD. Fluid turbulence. Whatever. And effectively to come up with a formula for what happens in the system.

And in a sense that's pivotal to the whole self-image of theoretical physics. That it should let one create theories that predict things. I mean, to find out what happens in a two-body problem of an idealized planet orbiting a star, one might have to explicitly trace every step in the orbit. But theoretical physics proudly tells one that one doesn't need to. It just gives one a formula for the result. That reduces the problem of prediction to evaluating a formula.

So how far can one push this approach? Is it just a matter of time before there are formulas for everything?

Within traditional physics or mathematics itself, there's really no way to talk about such questions. But the new kind of science that I've spent a long time developing definitely has things to say.

Remember that its foundation is to talk about what happens with all possible simple programs—all possible sets of rules. Traditional exact sciences have been very math-centric. Talking only about things that can be formulated in terms of traditional mathematical constructs. Well, now with NKS we get to take a much broader view. To explore the whole computational universe of possible kinds of underlying rules.

So what do we find? A good example is my favorite collection of one-dimensional cellular automata. Here are a bunch of them.

Enlarge Image

Many do fairly simple things. They make uniform patterns. Or at least repetitive ones.

And we can readily imagine that we can find a formula for what these do. That tells us, for example, whether any square at any position and step will be black or white.

But what about this guy? My favorite rule 30?

Enlarge Image

Is there a formula for what happens after a certain number of steps?

Or this one?

Enlarge Image

I don't think so.

I think, in fact, that systems like this are fundamentally what I call "computationally irreducible."

We can think about a system like rule 30 as doing a computation. And when we try to predict what it's going to do, we're doing a computation too. And in a sense the traditional successes of areas like theoretical physics have really been based on us somehow doing more sophisticated computations than the systems we're studying. So that we can shortcut things, to find out what the system will do with a lot less computational effort than it takes the system itself.

Well, one of the foundational ideas in my book and my science is what I call the Principle of Computational Equivalence. Which says that actually almost all systems whose behavior is not obviously simple are ultimately exactly equivalent in their computational sophistication. So even though our brains and our mathematics may operate according to some pretty complicated rules, they ultimately can't support computations that are any more sophisticated than what happens in something like little rule 30. So that means that the behavior of rule 30 is computationally irreducible: we can't figure out what it will be by any progress that's much more efficient than just reproducing each step.

So that means that we can never get what one might think of as an "exact solution" to rule 30—say a formula based on position and time that immediately tells us what color a cell will be.

By the way, to prove this one of the things one would do is to show that rule 30 is computationally universal—so that in effect it can do any computation—emulate any system. And that's a way to understand why it can't have an exact solution. Because in a sense within that solution would have to be any possible computation. Which means it can't be just a short formula of any kind.

Well, OK, what does this mean for special functions? Well, if there's a lot of computational irreducibility out there, then special functions won't be terribly useful. Because it won't be possible to make formulas—with special functions or anything—for lots of problems.

And one of the big results of my book and my science is that if one just looks out there in the computational universe of possible programs, computational irreducibility is actually very common. And really the reason we haven't seen more of it is that areas like theoretical physics have pretty much defined themselves specifically to avoid computational irreducibility.

In nature, though, and particularly in areas like biology, there seems to be a much broader sampling of the computational universe. So there's lots of computational irreducibility out there. Which theoretical science hasn't so far been able to make much progress on.

But OK, so we look at some system like rule 30—or let's say something like the little nonlinear PDEs that I found from sampling the space of possible PDEs.

Enlarge Image

Why can't there be some new higher-level special function that captures what's going on in these systems?

Well, of course, we could perfectly well just define a rule 30 special function. Or a special function for this PDE. But that's kind of cheating. And the way we'd find that out is by seeing that that special function would be too special. Sure, it would nominally let us shortcut rule 30, or this PDE. But that's all it would do. It wouldn't be like a Bessel function, that shows up in zillions of seemingly different problems. It would just be a lookup for this particular problem.

Well, OK, so what's the more general picture? The point is that when there's computational irreducibility, it means there are lots of separate "spurs" of computational ability. To have something like a special function, and to have it be useful, there must be large "basins" of problems that are all easily reducible to that particular special function.

So there seems to be an area of problems that are all reducible, and involve the standard hypergeometric-style special functions. But what about beyond that? My guess is that it's full of computational irreducibility. And in a sense very fragmented. So that there can't be some magic new kind of special function which could immediately "grab" lots of new problem areas. It's a little like what's happened with solitons and so on. They're neat as far as they go. But they somehow seem to be very specific. They're living on some very specific spur in the space of possible problems.

OK, so how can we formulate these notions a little more?

We can think about the analogs of special functions for many kinds of systems. Are there limited sets of special objects that may take effort to compute, but from which lots of other useful objects can easily be reached?

We could ask that for numbers, for example. Where the "elementary numbers" might be the rationals, and the algebraic numbers. What are the useful "special numbers"? Well, of course we have Pi, and E, and EulerGamma. What about other constants? Curiously, they seem to fall off in usefulness very quickly after the very well-known ones. There don't seem to be a lot of cases in the Wolfram Functions Site, for example, where we have a single constant that comes up, but we don't have a name for it.


[Recording ends at this point]

[There are additional notes, which may be included at a later date]

Publications by Stephen Wolfram »