Sunday, December 27, 2009

On biggest numbers

There's a quite long, but very interesting essay on big numbers. Here:
Author describes math competition to write down a representation of as big as possible number in 30 seconds. It's quite interesting thing to read as it stretches your imagination.
The biggest joy was to read about 'Busy Beaver' numbers. Those are amazing. But there's one mistake IMO. While it's possible to prove that busy beaver numbers sequence grows faster than any other computable sequence, it doesn't let you win biggest number competition. It only says that for each 'opponent' sequence there exists some number N starting from which Busy Beaver sequence will be greater than that sequence. And you will still need to prove, that, say busy beaver sequence number 1111 is greater than Ackermann's number 1111. For example BB(4) is only 107, while Ackermann's 4th number is quite large - around 10E154.
It may be quite tricky to judge such competition. For estimating largest entries we can use floating point numbers for computation, but it seems that we can easily meet such big entrants that resulting floating point mantissa representation will exceed available computer memory! So we may need to use floating point number approximation for mantissas! It's not hard to imagine yet another level of floating approximation of mantissas.
Computation time can also be challenging and may require special methods. How about estimating A(1E1111) ? My math skills and available computation facilities do not allow me to get even estimation of that number in my entire lifetime. But it should be truly huge number.

No comments:

Post a Comment