From ca6d9b4c0a40ec6c5ca72ce6879d28229f351579 Mon Sep 17 00:00:00 2001 From: couturie Date: Sun, 25 Mar 2012 19:56:45 +0200 Subject: [PATCH 1/1] 2 --- turing4complexity.tex | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) 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} -- 2.39.5