The big numbers don't impress me, but the fact that such tiny machines can correspond to complex and even meaningful theorems is fascinating. I wonder what the smallest number of states you need to encode a pre-existing well-known mathematical conjecture is.
They've found a 43-state machine that encodes the Goldbach Conjecture, and proposed but not verified that it can be compressed 27 states. I would consider the Goldbach Conjecture to be "well-known" as far as math theorems go, since it was referenced on Futurama.
