The Limits of Computation
Some problems no computer can solve, others none can solve fast enough, and finite precision bounds what any calculation can know.
Not Everything Is Computable
There are well-defined problems that no algorithm can solve, ever, on any computer. The classic example is the halting problem: no general procedure can decide, for every program and input, whether the program will eventually stop. These undecidable problems mark a hard boundary that no faster hardware crosses; they are impossible in principle, not merely in practice.
Solvable but Intractable
Beyond what is computable lies what is computable in acceptable time. Many important problems have only algorithms whose cost explodes with size, so that even modest instances would take longer than the age of the universe. The theory of computational complexity classifies problems by this scaling, and for the hardest, no efficient algorithm is known and quite possibly none exists.
Physical and Numerical Limits
- Finite precision: floating-point arithmetic bounds how accurately any real quantity can be represented and computed.
- Chaos: in chaotic systems, tiny input errors grow exponentially, capping how far ahead prediction is meaningful.
- Ill-conditioning: some problems amplify input error so much that no algorithm gives a trustworthy answer.
- Physical limits: energy, memory, and the speed of light bound real machines.
Chaos and the Horizon of Prediction
Even a perfect model and a perfect computer cannot predict a chaotic system indefinitely, because unavoidable uncertainty in the initial state grows until the forecast is worthless. This is a limit on knowledge, not on effort, and it is why some predictions are inherently probabilistic rather than exact.
Why It Matters
Knowing these limits keeps expectations honest: not every question has a computable answer, not every computable answer is affordable, and not every affordable answer is precise or far-reaching. Scientific computing works within these bounds, choosing tractable approximations and stating how far a prediction can reach, including in the study of turbulent, chaotic plasma behavior.