of choosing the first bits in with probability given by , and the remaining bits uniformly at random. We have thus: We thus have (a simple calculus trick shows this), thus distributions and can be distinguished by . Without loss of generality, we can assume that , with a polynomial. This gives us a possible construction of a Turing machine solving the next-bit test: upon receiving the first bits of a sequence, pads this input with a guess of bit and then random bits, chosen with uniform probability. Then it runs , and outputs if the result is , and else. References Pseudorandom number generators