2012/10/17 by Pavel Pudlak, Pudlak, Pavel
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO
paper · pdf · doi:10.48550/arxiv.1210.4692
arxiv created 2012/10/17 · arxiv updated 2012/10/18
Pseudorandmness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To this end we construct a set of models \cal M, a common element ι of these models and a probability distribution on \cal M, such that for every pseudorandom sequence s, the probability that s(ι)=1 holds true in a random model from \cal M is equal to 1/2.