Visualization and dataset preparation

We also provide a bdm.ipynb Python jupyter notebook that:

1. Read data outputed by LBA enumeration program
2. Compute symmetries of generated strings
3. Read data from original BDM binary 1 dimension Turing Machine model
4. Compare both models complexities distributions and plot visualizations
5. Serialize LBA distribution data in the format required for the Block Decomposition Method

Python was used for both ease to work with visualization and integration with pybdm itself.

Dependency/usage

The notebook requires many packages, that are listed in the beginning. Also requires the ctm_data folder from pybdm to be located (copied) to the directory where the notebook resides. This folder contains the dataset used by pybdm and is where we load the turing machine model from and where we write the linear bounded automata one.

The notebook follows the steps described here, and its cells should be executed in order.

On symmetry

In our simulation model (see reference) we fill the tape with '1's and we start in the first position to the left. To account for reflection and inversion symmetry, each of our produced strings ocurrence should actually represent 4 ocurrences: original, inverted (flipping bits), reflected (transposing right to left), inverted AND reflected.

As an example, an ocurrence of 1011 should represent:

• One ocurrence of 1011
• One ocurrence of 0100 (inverted)
• One ocurrence of 1101 (reflected)
• One ocurrence of 0010 (inverted AND reflected)

This procedure is done in the mentioned notebook file.