Solvable Problems
© 12 November 2012 Luther Tychonievich
Licensed under Creative Commons: CC BY-NC-ND 3.0
other posts

There are a few problems we know how to solve. The rest get reduced to these.


A Church-Turing Thesis asserts that if it can be done, it can be done by a computer. So far we know of no reason to doubt this thesis. But when you start looking at what computers actually do it is impressive how few problems they actually solve.

One of the problems areas computers can solve is linear algebra. Eigenvalues and matrix manipulations are everywhere. Anytime you hear the words “‍computer simulation‍” or see a computer interacting with real-world objects you can safely assume linear algebra is at work.

Linear algebra is just the study of linear systems of equations. We all remember these from school: “‍if x + y = 9 and 2xy = 3, what are the values of x and y?‍” When I was first introduced to linear systems of equations I thought them silly, contrived, and pointless. Which, as presented, they were. But they are also the basis of iterative approximation.

Iterative approximation springs from Newton’s first law: “‍An object in motion tends to remain in motion unless acted upon by an outside force.‍” Things don’t change all at once. Over a small enough time window, everything seems to be moving at a constant rate. And things changing at a constant rate are expressible as linear equations.

The simplest example that comes to mind is a ball flying through the air. The ball is spinning, the air is moving, there’s gravity and drag; we really don’t want to try to solve the entire motion equation all at once. So instead we express the linear aspect of each force at one moment in time and use that linear approximation to find where the ball will be a fraction of a second later. Then we repeat, finding a new linear equation and moving forward another fraction of a second, thousands of times until we figure out what we wanted to know.

In practice, there are many things to consider when designing such an iterative process. There are many ways to approximate a problem linearly and each has different trade-offs. Do we model velocity or energy or both? How many numbers do we use to represent the motion of a fluid or the stresses on an I-beam? Do we approximate things with a grid because it is easier to compute or with more arbitrary regions because they match the shape of the real world more closely? Etc.

But all of the interesting design questions aside, a lot of computing comes down to linear algebra. It’s one of the few problems we can actually solve.

Looking for comments…

Loading user comment form…