1
$\begingroup$

Suppose I have a random number generator G that takes in a seed s from the set of integers. Suppose we have a sequence of numbers Q where |Q| = k. Does there exist a seed s such that G(s) produces the sequence Q, for any Q with any length? This is an existence question; does it exist or not, the process of finding a random number generator is irrelevant. The code for G is finite as is the seed s.

My intuition is that no, moreover, it's impossible to construct such a G with these properties. Unfortunately I can't justify my intuition.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ In case k > cycle length it always fails, so any length prevents it. $\endgroup$ – Evil Mar 21 '18 at 0:13
2
$\begingroup$

If you are considering a pseudorandom generator that can work with seeds of any length, then the answer is "It depends". It depends on the pseudorandom generator. There are pseudorandom generators for which the answer is yes (e.g., $G(x)=x$, or any bijective $G$), and pseudorandom generators for which the answer is no (e.g., $G(x) = G'(\text{SHA256}(x))$, where $G'$ is a pseudorandom generator that accepts fixed-length seeds, is almost certainly such an example).

In practice, pseudorandom generators usually have a fixed-length seed. In that case, if the length of the output is longer than the length of the seed, then there exists an output that isn't produced by any seed (of that length). This follows from the pigeonhole principle.

In practice this almost certainly doesn't matter. Usually what matters is whether the output of the pseudorandom generator passes statistical tests, or whether it is indistinguishable from true-random bits.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This was insightful! Now a followup question, if we allowed infinite bits, then it is possible, correct? However, would this be out of the definition of a Turing Machine? If the Church-Turing Thesis is correct, wouldn't that imply that true randomness can't exist in the natural world? $\endgroup$ – War Donkey Mar 21 '18 at 1:56
  • 1
    $\begingroup$ @SpentDeath, I don't know how to think about what it means for an algorithm to work on infinitely many bits (as opposed to a finite but unlimited number of bits). Probably someone has thought about how to formalize that, but it's beyond my knowledge. Sorry. Yes, it's beyond the definition of a Turing machine. It has zero implications for the Church-Turing thesis, as the Church-Turing thesis is about what can be implemented in practice, and a computation on infinitely many bits isn't something that can be done in practice. $\endgroup$ – D.W.♦ Mar 21 '18 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.