4 ms·
Why? Is it because it haven't been found, or is there a proof of impossibility?
by ffhhj 4y ago
Why? Is it because it haven't been found, or is there a proof of impossibility?
- krapp 4y agoAny conceivable sequence could theoretically be generated by randomness. A perfect random number generator could generate a list of social security numbers or an infinite sequence of zeros. Likewise any sequence that appears random may just have a pattern which hasn't emerged from what has observed.
- lmm 4y agoIt would require P=NP (widely assumed to be false) and the nonexistence of one-way functions (actually an even stronger assumption). Any one-way function can be used as a PRNG, and it's computationally infeasible to distinguish that from a true random number generator, almost by definition.
- orangecat 4y agoAssuming "random" means that there is no program to generate the sequence that is shorter than the sequence itself, proving the nonexistence of such a program is equivalent to the halting problem. See https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
- Someone 4y agoIf you observe a black box producing a sequence N items, you can’t know whether it will, after that, repeat the same sequence at infinitum (it might just contain a circular tape of N items, for example), or keep producing a single identical item, or keep producing only two different items, etc.