turing4complexity.tex

   1 \documentclass{article}
   2
   3 \title{Using complexity of short strings to define new statistical tests for PRNGs}
   4
   5
   6 \begin{document}
   7 \maketitle
   8
   9
  10 \begin{abstract}
  11 blabalbabla
  12 \end{abstract}
  13
  14
  15 \section{Introduction}
  16
  17 \section{Algorithmic complexity for short strings}
  18
  19 In their paper, they introduced a method to compute the complexity of D(n).
  20 With D(4), 5 970 768 960 machines halt. There are 1832 different strings.
  21
  22 \section{PRNG preserve distribution of short strings}
  23
  24 In this section, we propose to measure the quality of a PRNG by considering that
  25 a good PRNG must preserve the distribution of short strings. More precisely, the
  26 pseudo-random  numbers obtained  by a  PRNG can  form the  states of  the Rado's
  27 original  Busy Beaver. Then,  machines obtained  by such  a construction  can be
  28 executed and if the PRNG is good, machines should generate the same strings with
  29 the same distribution than the theoretical Busy Beaver (with all the enumeration
  30 of states).
  31
  32 \end{document}