3.7. Lab 6: Cellular Automata

Due Date: 9:59pm February 16, 2024

Labs received by 11:59 February 18, 2024 will not be penalized

Labs should be submitted as a single Jupyter notebook to CourseLink Dropbox

This lab counts for 4% of the final grade

3.7.1. Exercises

Complete the exercises below. These reference the content in Chapter 5 of Think Complexity (version 2):

  1. Run the code in Allen Downey’s Chapter 5 notebook. Make sure you are comfortable with the Cell1D class as you will use it in the following exercises. Report your results at the end of the Chapter 5 notebook.

  2. (Exercise 5.1 from Think Complexity) Write a version of correlate that returns the same result as np.correlate with mode='same'. Hint: use the NumPy function pad. Note that this exercise is embedded in the notebook.

  3. (Exercise 5.2 from Think Complexity) This exercise asks you to experiment with CA Rule 110 and see how many spaceships you can find.

    1. Read the Wikipedia page about Rule 110, which describes its background pattern and spaceships: https://en.wikipedia.org/wiki/Rule_110.

    2. Create a Rule 110 CA with an initial condition that yields the stable background pattern.

      Note that the CA class provides start_string, which allows you to initialize the state of the array using a string of 1s and 0s.

    3. Modify the initial condition by adding different patterns in the centre of the row and see which ones yield spaceships. You might want to enumerate all possible patterns of \(n\) bits, for some reasonable value of \(n\). Visualize your findings. For each spaceship, can you find the period and rate of translation? What is the biggest spaceship you can find?

    4. What happens when spaceships collide?

You are required to complete one of the two following exercises, but not both:

  1. (Exercise 5.3 from Think Complexity) The goal of this exercise is to implement a Turing machine.

    1. Read about Turing machines at https://en.wikipedia.org/wiki/Turing_Machine.

    2. Write a class called Turing that implements a Turing machine. For the action table, use the rules for a 3-state, 2-symbol busy beaver.

    3. Write a draw method that plots the state of the tape and the position and state of the head. For one example of what that might look like, see https://mathworld.wolfram.com/TuringMachine.html.

  2. (Exercise 5.4 from Think Complexity) This exercise asks you to implement and test several PRNGs. For testing, you will need to install DieHarder, or it may be available as a package for your operating system.

    1. Write a program that implements one of the linear congruential generators described at https://en.wikipedia.org/wiki/Linear_congruential_generator. Test it using DieHarder.

    2. Read the documentation of Python’s random module. What PRNG does it use? Test it and report your results.

    3. Implement a Rule 30 CA with a few hundred cells, run it for as many time steps as you can in a reasonable amount of time, and output the centre column as a sequence of bits. Test it and report your results.

3.7.2. Notes

Question 3 makes use of the DieHarder random number generator (rng) and testing suite. This package has been installed on the lab computers and allows you to generate streams of random numbers and test how random a stream is. The simplest way to do this at the command line is to pipe the raw binary output from the generator directly into dieharder. The following example illustrates sending a random stream of bits from /dev/urandom to dieharder and running all the tests in the full test suite:

$ cat /dev/urandom | dieharder -a -g 200

The above example starts by connecting a pipe from the output of the cat command to the input of dieharder. The cat command is simply reading a continuous stream of random numbers from the /dev/urandom device. The -g 200 option tells dieharder to use stdin as the input stream. For a full list of generators that dieharder supports run dieharder -g -1. The -a flag tells dieharder to run all the available tests on the given input stream. You can use dieharder -l to list all available tests and the -d <TEST> command to specify individual tests to run. Running all the tests with -a may take a really long time.

Dieharder can also accept files for the rng input. If the file (or stream) includes a finite set of random numbers, tests that require more numbers than are available will either fail or rewind the file and cycle through it again (and again as needed).

In Question 3 you are asked to write a program that implements one of the linear congruential generators described at https://en.wikipedia.org/wiki/Linear_congruential_generator. To test it using dieharder in the context of a Jupyter Notebook you have quite a few options. A basic example is described below but feel free to get more adventurous with streams/pipes if you feel like more of a challenge.

The most straightforward solution is to generate a file with the necessary file header to describe the numbers it contains. After generating this file you can run dieharder with -a -g 202 -f <FILENAME> to specify that the input comes from FILENAME. To get an example of the required format run the following command:

$ dieharder -o -f example.input -t 10

The above command will output 10 random numbers using the default generator into the file ‘example.input’. You will need to modify the following fields in the header you create for testing.

generator <NAME>

The name of the generator. This serves to document where the generator comes from.

seed = <SEED_VAL>

The initial seed value.

count: <COUNT>

Specifies how many random numbers are included in the file.

numbit: <NUMBIT>

Specifies the number of bits of each random number.

Your Jupyter Notebook should do the following:

A more advanced solution would be to create a stream and pipe the bits into dieharder using the Python pipe and subprocess interfaces.

3.7.3. Submission

Please submit your answers to the above exercises appended to the end of Allen Downey’s Chapter 5 notebook.