*The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us*(MIT Press, 2013). Written for the layman, it explores the realm of the unsolvable, unprovable, and unknowable. Some (perhaps even most) of the material will be familiar, but Yanofsky offers a compelling synthesis of various “outer limits” problems.

Some computing challenges are staggering—that is, practically unsolvable, even if not theoretically impossible. For instance, Euler may have solved the seven bridges of Königsberg problem with sheer brain power, but solving the traveling salesman problem for 100 cities—assuming that our computer can check a million routes in a second—would take 2.9 * 10

^{142}centuries! Splitting a hundred numbers into two sets to see if the sum of one part equals half the sum of all the elements would take a

*mere*401,969,368,413,314 centuries. And trying to predict with any degree of precision an event in a chaotic system, or a complex adaptive system, is a pretty hopeless undertaking; it’s not even a question of time or computer power. (Just ask any trader.)

Many problems, such as the halting problem or the tiling problem, are undecidable—at least by computer logic. Often these problems suffer from some form of self-referential limitation. Think of time-travel paradoxes, Russell’s paradox, Gödel’s first incompleteness theorem or my personal stroll-down-memory-lane favorite (I guess because, when I was first introduced to logic, I learned a new word in the process) the heterological paradox. In fact, Yanofsky writes, “the universe is the ultimate self-referential system; the universe uses scientists to study itself.” (p. 343)

Other problems stem from the chasm between the describable and the indescribable—the former countably infinite, the latter (presumably) uncountably infinite. That is, “there is no longest word or longest novel, because there is no limit to the longest formula, and so on. This makes language infinite. However, it can be alphabetized or counted, which makes language countably infinite. … It is plausible to say that there is an uncountably infinite number of phenemona that can occur. This is stated without proof because I cannot quantify all phenomena. To quantify them, I would have to describe them and I cannot do that without language.” (p. 175)

Yanofsky doesn’t break new ground in this book, but he offers a “one-stop” emporium for those who enjoy pondering the limits of reason. I had a grand time reading it.

The travelling salesman problem has been solved to a provably optimal solution to a search space of 85,900 towns using MIP (mixed integer programming) methods. To put this in perspective, 100 towns would have 100! = 9.3e157 permutations, whereas 85900! = 9.6e386526 .

ReplyDeleteSource: Wikipedia TSP article