1.Previous
3.Next

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

1.Previous
3.Next