The Risch Algorithm

Differentiation is a solved problem: give a computer any formula built from polynomials, exponentials, logarithms and trigonometric functions, and it can grind out the derivative every time, mechanically, using nothing but the chain and product rules. Integration looks like the same kind of task run backward — and for two centuries mathematicians treated "can this be integrated in closed form?" as a matter of trying harder.

It isn't. The integral $\int e^{-x^2}\,dx$, the heart of the normal distribution, has no expression built from the elementary functions — no matter how many substitutions or tricks you throw at it. Neither does $\int \frac{\sin x}{x}\,dx$ or $\int \frac{1}{\ln x}\,dx$. These are not failures of cleverness; they are theorems.

In 1969, Robert Risch turned that theorem into an algorithm. Given an elementary function, the Risch algorithm decides — in a finite, mechanical process, not an open-ended search — whether an elementary antiderivative exists, and if so, constructs it. It is one of the rare corners of mathematics where "this cannot be done" is not a shrug but a proof, delivered by a machine.

Pick an integrand below. For each one, a simplified version of the Risch machinery — comparing the shape of the derivative you'd need against the shape the function actually has — reports whether an elementary antiderivative exists, and shows it when it does.

<p class="hint">{{hint_para}}</p>
<div class="picker" id="picker"></div>
<div class="btns">
  <button id="decide" type="button">{{btn_decide}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="result" id="result">{{pick_hint}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.picker { display: flex; flex-direction: column; gap: .4rem; margin: .4rem 0 .8rem; }
.opt { display: flex; align-items: center; gap: .55rem; padding: .5rem .7rem; border: 1px solid #cdd9e3;
       border-radius: 8px; background: #f4f7f9; cursor: pointer; transition: all .1s; }
.opt:hover { background: #e8eef3; }
.opt.sel { background: #1d3557; border-color: #1d3557; color: #fff; }
.opt .fn { font: 700 15px ui-monospace, monospace; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 3.2em; line-height: 1.5; }
.result.yes { color: #0a7d33; }
.result.no { color: #c92f3c; }
.result .antideriv { font: 700 15px ui-monospace, monospace; display: block; margin-top: .25rem; }

// Code not found

Notice the pattern: functions like $x e^{x^2}$ integrate cleanly because the extra factor of $x$ is exactly the derivative the exponent needs. Drop that factor, as in $e^{-x^2}$, and the same machinery can certify — not just fail to find — that no elementary formula exists.

Why can't you just try harder substitutions on $e^{-x^2}$? Because "harder" has no upper bound — an infinite search is not a decision procedure. The Risch algorithm's achievement is turning an apparently infinite search into a finite, terminating one.

• Liouville's theorem (1835) is the seed: if an elementary function $f$ has an elementary antiderivative, that antiderivative must have a very restricted algebraic shape — essentially $f$'s own field of functions plus a finite list of logarithms of things already in that field, with constant coefficients. There is no room for a mysterious new ingredient to sneak in.
• Differential fields make this precise. Risch treats each class of functions (rational, then adding exponentials, then logarithms, one "transcendental extension" at a time) as an algebraic structure with a derivative operator, and asks a purely algebraic question: does a solution of the required shape exist in this field?
• The algorithm is recursive and constructive. At each extension it either produces the missing piece of the antiderivative or proves, via a polynomial-degree argument, that no such piece can exist — which is exactly what happens for $e^{-x^2}$: the theorem shows the needed antiderivative would require a new logarithmic term that cannot appear, so none exists.
• It decides, it doesn't search. This distinguishes the Risch algorithm from most of the impossibility results native to this site, like the undecidability of the halting problem — integrability of elementary functions is a case where an infinite-looking question turns out to be fully decidable, with a proof of "no formula exists" as concrete as the formula itself would have been.

The real algorithm (as implemented in computer algebra systems) is a large, delicate piece of engineering — it must handle nested radicals, algebraic extensions and the notorious "risch integration problem" of choosing constants correctly — but the logical core is exactly this: reduce calculus to algebra, then let algebra decide.

Knowing exactly when a closed form exists — and being able to prove it doesn't — reaches far beyond a classroom exercise:

• Computer algebra systems: Mathematica, Maple and Sympy's integrate commands run variants of the Risch algorithm (extended by later work on special functions) to return an exact antiderivative or correctly report that none exists in elementary terms.
• Special functions: when the Risch algorithm proves no elementary antiderivative exists, that failure is precisely why mathematicians invented the error function, the sine integral and the logarithmic integral — new functions built to name what elementary functions cannot express.
• Numerical methods: knowing in advance that $\int e^{-x^2}dx$ has no closed form justifies using numerical integration or series expansions instead of futile symbolic search — it converts "we couldn't find a formula" into "no formula exists."
• Differential algebra as a field: Risch's approach seeded decades of work on decision procedures for algebraic and differential structures, echoing the broader theme of the limits of computation explored throughout the Church-Turing thesis and computability theory.

Every time software confidently tells you an integral "has no elementary solution" rather than merely giving up, that confidence traces back to Risch's 1969 decision procedure.

The Risch algorithm answers a question that looks philosophical — "can this be done at all?" — with the tools of pure algebra, and does so in a finite, mechanical number of steps. $e^{-x^2}$ was never waiting for a cleverer substitution; there genuinely is no formula, and the algorithm proves it the same way it would construct one if it existed.

That is a small, precise instance of a much larger idea running through this site: some questions about what can be computed, expressed or solved have definite answers, and finding the boundary is itself an algorithmic achievement — a cousin, in spirit, of the same decidability questions raised by P vs NP.