X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/turing4complexity.git/blobdiff_plain/8729d89ff655085d7e4f6342d03df1a6eeff2e5b..ca6d9b4c0a40ec6c5ca72ce6879d28229f351579:/turing4complexity.tex?ds=sidebyside

diff --git a/turing4complexity.tex b/turing4complexity.tex
index e69de29..bbc2e69 100644
--- a/turing4complexity.tex
+++ b/turing4complexity.tex
@@ -0,0 +1,32 @@
+\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{PRNG preserve 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).
+
+\end{document}