@Evil OK. Well, PRNGs are normally evaluated under the model that the only thing that is unknown is the seed (the true-random inputs). If the other things are not known, presumably there is some process that created them, so there is some probability distribution on them. In principle one could specify the process and distribution on them and the problem would be well-defined, but reasoning about that kind of situation is messier.
For instance, if all feedback functions are possible and equally likely, then it will probably take about $2^{n/2}$ bits of output to distinguish the output from true-random, where $n$ is the length of the state. But in practice it's rare for feedback functions to be chosen that way, for a number of reasons: usually they're chosen from a smaller set (e.g., faster to evaluate, etc.), and then the PRNG might be worse than this comment would otherwise indicate.
@mirgee not an expert on this but suspect proof works for c^k for any constant c, here on wikipedia c=10 is chosen, maybe worth asking on site. (wikipedia is not so good for deeper/ more nuanced explanations sometimes, eg math thms etc)
