Tuesday, August 21, 2012

Introduction to The Divine Random

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.
Does true randomness truly exist?

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)
The question of whether such universally unpredictable events actually exist in our universe gets very deep very fast. It quickly bumps up against some of the most enigmatic and fundamental principles of physics, mathematics, computation, and theology. Together, these principles define the boundary of the known universe. And by that, I don't mean just the limit of what we know today, to be extended as we learn more tomorrow. I mean the absolute limits of science and reason, beyond which we can 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.

2 comments:

  1. 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.

    In 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.

    ReplyDelete
  2. 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