# Chaitin’s version of Gödel’s theorem and pseudorandomness

Chaitin’s version of Gödel’s theorem roughly states that there exists a constant c such that for each string of one’s and zeroes x, the sentence “the algorithmic information complexity (Kolmogorov complexity) of x is greater than c” is unprovable, even though there are an infinite number of x’s in which the sentence is true.

I am wondering if it were possible to prove an analogous statement in computational complexity theory with respect to pseudorandomness - that for each function f, the sentence “f is a pseudorandomn number generator” is unprovable, even though there are maybe many such functions f in which the sentence is true.

Is there anything in the literature that addresses this question?

• The problem with proving or disproving that "f is a pseudorandom number generator" is defining "pseudorandom number generator" formally. There is a way to capture "randomness" in computational complexity theory: a sequence is random if it requires as many bits to describe a generator as there are in the sequence. Essentially, this means it is not compressible using any compression method; the decompression "code" is always as big or bigger than the sequence. Commented Apr 4, 2023 at 0:06
• I have in mind the normal definition of pseudorandomness in computational complexity theory, not compression, since that is algorithmic information theory. Commented Apr 4, 2023 at 0:25
• Unlike ML randomness in AIT, intuitively pseudorandomness doesn't have an algorithmic constructive definition, only with some classes of statistical tests criterion to do binary classification. Notice in below answer's wikipeadia link for the classes of Boolean circuits of a given size, its corresponding PRG's existence has not yet proved while it's known to be related to the circuit's lower bounds in computational complexity theory, so maybe you could search reference therein to see if such existence is actually abundant or not. Commented Apr 4, 2023 at 5:29