Monday, October 5, 2009

why george chaitin cannot find a smallest program?

He tells that in experiment of coin tossing, we get a sequence of finite length. He also tells that size of a (best) program must be less than the sequence to compress and that we can traverse all the programs (of size < sequence) looking if it compresses the sequence.