Eliezer, you are mistaken that eliminating half of the population gives only 1 bit of mathematical information. If you have a population of N individuals, there are C(N,N/2) = N!/((N/2)!*(N/2)!) different ways to eliminate half of them. See http://en.wikipedia.org/wiki/Combination. Therefore it takes log_2(C(N,N/2)) (which is O(N)) bits to specify how to eliminate half of the population.
So, it appears that with sexual recombination, the maximum number of bits a species can gain per generation is min(O(G^0.5), O(N)).
Oh, sending 10 bits each with a 60% probability of being correct actually lets you send a total of just 0.29 bits of information. Each bit in this communications channel gives the receiver only 0.029 bits of information, using a formula from http://en.wikipedia.org/wiki/Binary_symmetric_channel. But, the amount of information actually received still grows linearly with the number of bits put into the channel.
Eliezer, you are mistaken that eliminating half of the population gives only 1 bit of mathematical information. If you have a population of N individuals, there are C(N,N/2) = N!/((N/2)!*(N/2)!) different ways to eliminate half of them. See http://en.wikipedia.org/wiki/Combination. Therefore it takes log_2(C(N,N/2)) (which is O(N)) bits to specify how to eliminate half of the population.
So, it appears that with sexual recombination, the maximum number of bits a species can gain per generation is min(O(G^0.5), O(N)).
Oh, sending 10 bits each with a 60% probability of being correct actually lets you send a total of just 0.29 bits of information. Each bit in this communications channel gives the receiver only 0.029 bits of information, using a formula from http://en.wikipedia.org/wiki/Binary_symmetric_channel. But, the amount of information actually received still grows linearly with the number of bits put into the channel.