A Study of Randomness in the Output of Simple Programs

Andrew Musselman
Central Washington University

In his book A New Kind of Science, Stephen Wolfram discusses the appearance of random behavior in nature and in the output of various simple programs. He describes three mechanisms for generation of such randomness and presents examples of each [NKS, p. 299-326].

We present work done in a project to study the existence and nature of random behavior present in the output of cellular automata and related systems. We have implemented in Mathematica code a suite of statistical tests for analyzing the random behavior in a sequence of binary data. These tests were taken from the Random Number Generator Test Suite developed by the National Institute of Standards and Technology [NIST]. We have applied these tests to data sets created from the output of various cellular automata, e.g., the center line of the output of rule 30 starting with a single black cell (This data set is, as expected, judged random by all tests we have run.) We have also applied the tests to other subsets of the output set: other vertical slices, horizontal slices, and various diagonals. We have also tested output sets resulting from running CAs starting with randomly chosen initial conditions and also from adding random noise to the normal output of a CA. We will present a selection of these data sets and the results of the statistical analyses.

[NKS] Wolfram, Stephen, A New Kind of Science, Wolfram-Media, Inc., 2002.

[NIST] Ruhkin, Andrew, et al, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications,” National Institute of Standards and Technology (NIST Special Publication 800-22), May, 2001.

Created by Mathematica  (April 20, 2004)