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.