# Computing the Kolmogorov complexity of a string

What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?

• It (potentially) depends on the running time of your algorithm. Aug 25, 2017 at 15:28
• The generator is based on feedback shift registers with the length of each register being 63 bits, so running at 10mhz ( 10 million bits per second) the cycle time is around 5000 years before the cycle repeats, is that what you mean by run time? Aug 25, 2017 at 15:35
• I meant the running time of your algorithm for computing the Kolmogorov complexity. Aug 25, 2017 at 15:35
• This is not what I asked. What is the running time of your algorithm for computing the Kolmogorov complexity of a string generated by a PRNG? Aug 25, 2017 at 16:08
• @Ariel Yes, I guess you're right. I was under the impression that the diagonalizing program should also belong to the infinite computable set, but I guess I was just daydreaming... Aug 25, 2017 at 20:36

If we're talking about a generator who can handle any length $n$ seed (perhaps this is more cryptographic PRG oriented), and stretch it to some length $n'>n$ pseudorandom string, then the answer is no. The reason actually has nothing to do with the properties of PRGs, but simply relies on the fact that the output of the generator is computable, and that its range is infinite.
• This is not possible (as the answer shows), so it's like asking what are the implications of $1=2$. Aug 26, 2017 at 6:21