I suppose it would be possible to "diagonalize" over all shorter programs for computing Pi. 1. Compute Pi to N digits. 2. Examine all arithmetic expressions of length log(log(N)), log(N), etc. 3. output the expression which computes the closest approximation to Pi for N digits. Hopefully, at some point, there is a program of _constant_ length that wins every time for N > some fixed constant. At 10:32 PM 10/14/2012, Henry Baker wrote:

At 08:29 PM 10/14/2012, Eugene Salamin wrote:

...

A program that calculates pi to N places requires memory that grows as some function f(N), and f(N) must grow unboundedly large with N. This is true for any irrational, since a finite state machine eventually repeats, and thus can only calculate rationals. So perhaps the complexity of an irrational number can be characterized by the slowest growing memory needed for its calculation.

There is a tower of complexity based on Turing machine tape lengths, and a tower of complexity based on number of steps. The two towers are inter-related but are not (obviously) identical.

Computing pi is particularly simple, because it doesn't require emulating all Turing Machines with less tape or fewer steps before deciding what the answer should be.