\documentclass{article}

\title{Using complexity of short strings to define new statistical tests for PRNGs}


\begin{document}
\maketitle


\begin{abstract}
blabalbabla
\end{abstract}


\section{Introduction}

\section{Algorithmic complexity for short strings}

In their paper, they introduced a method to compute the complexity of D(n).
With D(4), 5 970 768 960 machines halt. There are 1832 different strings.

\section{Property: a PRNG must preserve the distribution of short strings}

In this section, we propose to measure the quality of a PRNG by considering that
a good PRNG must preserve the distribution of short strings. More precisely, the
pseudo-random  numbers obtained  by a  PRNG can  form the  states of  the Rado's
original  Busy Beaver. Then,  machines obtained  by such  a construction  can be
executed and if the PRNG is good, machines should generate the same strings with
the same distribution than the theoretical Busy Beaver (with all the enumeration
of states).  In  practice, PRNGs will not generate all  the strings with exactly
the  same  probabilities. Nevertheless,  the  distance  between the  theoretical
probabibilities and the obtained probabilities  with a PRNG is a good indication
of the quality of the PRNG.

In the following  we report our experiments. Let $S_i$ be  the string number $i$
obtained by the busy beaver, $S(n)$ is the set of strings of $D(n)$. With $D(4)$
there  are  1832  strings,  so  $|S(4)|=1832$.  $P_t(S_i)$  is  the  theoretical
probability of  the string $S_i$ and  $P_{PRNG}(S_i)$ is the  probability of the
string $S_i$  obtained with the execution of  a given PRNG. Let  For $D(n)$, the
number of strings is

\end{document}
