Does true randomness truly exist?Come travel with me, far from now and here,

To a niche carved into entropy.

A perfect island, in a magic sea,

Where only miracles and fools are feared.

We know that randomness is useful, essential even, in solving a number of important problems in distributed computing, social choice, and identity. It is also the case that truly comprehensive solutions to those problems require true randomness, not the more limited kind one typically finds in digital computing.

A Julia Island (Courtesy Wikimedia Commons) |

*never*venture, no matter how clever we are.

For a long time, I've been fascinated with a set of theorems that seem to define that boundary. They include the following:

**Heisenberg's Uncertainty**(Physics) — There is a limit to how accurately we can measure the properties of physical objects.

**Bell's Inequality**(Physics) — That limit applies not just to our ability to measure things accurately, but to our fundamental ability to*know*things about physical objects.

**Gödel's Incompleteness**(Mathematics) — Any attempt to explain everything using a small(er) set of axioms is doomed to be either unfinished or wrong.**Turing's Undecidability**(Computing) — There are infinitely many problems that cannot be solved by any digital computer.**Chaitin's Irreducibility**(Computing & Mathematics) — Almost every number (probability = 1) is "random" in the sense that it cannot be computed by an algorithm that is much shorter than the digits of the number. That is, the shortest*name*for the number is the number itself. Randomness exists in mathematics as well as physics!

I will talk more about these ideas and theorems in later posts in this series (informally of course - please don't confuse me for a real physicist or mathematician). For now, notice the last word in their names. Each of them expresses a negative. Each of them tells us something about what we

*cannot*do, where we

*cannot*go, what we

*cannot*, under any circumstances, know.

Intuition suggests these five principles, despite their different fields of application, are somehow related. In fact, they seem to be exactly the same, or at least stem from the same underlying phenomenon. Namely this:

Fundamental randomness exists. It isn't just a small wart on our logical world, but rather an unfathomable ocean surrounding it. We cannot ever know what goes on in this ocean of randomness. We can only glimpse the shape of the coastline of our little island of reason, as the theorems and principles listed above begin to illuminate.

I was struck by this same thought while reading Numbers Rule. While the book was nominally about the history of voting and apportionment methods, it brought up a connection between Arrow's impossibility theorem, the similar impossibility of "fair" apportionment, and, yes, Godel's incompleteness theorem.

ReplyDeleteIn the same way that two candidate elections are trivial, two-body physics problems are. And yet, three-body problems and three candidate elections, are hard. It feels like there's something to that.

Dale, I read Numbers Rule after your recommendation a while back. Thanks for that. I had forgotten the story of how Kurt Godel said he discovered a flaw in the US constitution that could lead to revolution and dictatorship. Depressingly, here we are today with an inevitably broken two-party system, a direct result of our constitutional voting methods, and a Texas judge suggesting civil war might result if the president is reelected. Scary.

ReplyDelete