Uncomputable Numbers and Determinism

A computable number is a number that can be calculated by a finite computer program. All the numbers you have ever heard of like 3, √2, π, e, etc. are computable. Some numbers (like π) are represented by an infinite string of nonrepeating digits. It would take an infinite amount of time to write all these digits down. Nevertheless, a finite computer can be programmed that would eventually print all of the digits of π. If irrational and trancendental numbers like √2, π, and e are computable, one begins to wonder if there are any uncomputable numbers. It turns out that almost every number is uncomputable. To understand this we first introduce the concept of a set being countable.

A set is called countable if it can be put in one-to-one coorespondence with the integers. For instance, rational numbers are countable. A rational number is a number that can be expressed as n/m where n and m are both integers. To show that rational numbers are countable, imagine a two dimensional square lattice of points where the points are labeled by their position.

The red line visits each of the points once. We can label the visits of the the red line with integers. The first visit is to point (1,1) the second is to point (1,2) etc. In this way we have put every point (n,m) in one-to-one coorespondence with the integers. This means that the rational numbers are countable. If we attempt to do the same thing with the real numbers we will find that it is impossible; the real numbers are uncountable. Mathematicians would say that the rational numbers form a set of measure zero along the real axis.

Computable numbers are numbers that can be calculated by a finite computer program. All rational numbers are computable. A finite program that prints a rational number would be:

print(n/m)

Many irrational numbers are also computable. For instance,

print(sqrt(2))

would print an irrational number. Any finite program can be expressed as a string of a finite set of text characters. To each member of set of characters we can assign a three digit integer between 100 and 999 like this:

a → 100      
   .              
   .              
z → 125      
A → 126      
   .              
   .             
Z → 151
0 → 152
   .
   .
9 → 162
( → 163
) → 164
+ → 165
* → 166
.
.
space → 400
newline → 401
 etc.

Using this mapping, we can assign a unique integer to any text file. Since finite computer programs can always be represented as a finite text file, the number of computable numbers is countably infinite.

This has consequences for mathematical operations that are sensitive to initial conditions. One of the simplist such operation is the baker's transformation. In this transformations a line segment is stretched to twice it's length and then folded back on itself. This is similar to the way that a baker rolls out dough.

Two points that start out near each other will eventually get pulled apart by this transformation. This means if you know approximately where the initial point is, you can predict about where about where it will be for a number of applications of the baker's transformation but you would have to know the initial condition exactly if you want to predict where it will be after an arbitrary number of iterations. If an initial point is chosen randomly then it will be an uncomputable number since there are so many more uncomputable numbers than computable numbers in the line segment. This means that it is not possible to predict the evolution of our point without supplying an infinite amount of information.

Many random number generators on computers are basically a baker's transform. Typically you start with some seed number between 0 and 1, multiply that by some very large number (the stretching) and then only keep the fractional part (the folding). Repeating this over and over results in a sequence of apparently random numbers.

Sometimes the equations that describe some natural phenomena have perform this same kind of stretching and folding. The equations that describe the weather are known to do this. This means that predicting the weather arbitrarily far into the future is impossible without knowing the current conditions (temperature, air pressure, humidity, wind speed, etc.) to arbitrary precision. Since the quantities that describe the weather are real numbers, they are uncomputable. No finite computer program can calculate the weather arbitrarily far into the future.

If the universe is a machine where the future is uniquely determined by its present state, it would not be possible to calculate what the future will be.