-
Notifications
You must be signed in to change notification settings - Fork 0
Documentation‐Wiki
This project is an extension of pybdm that allows calculating BDM (Block Decmposition Method) complexity of binary strings using Linear Bounded Automata instead of Turing Machines.
BDM and the necessary parts of the algorithmic information theory it is based on are described in this paper.
This Python programming package can be used for computer scientists, researchers on computer theory, information theory, that are interested in studying/calculating approximations of kolmogorov complexity. Research from other areas such as neuroscience, psychology and economy might also benefit from this package, considering the theoretical connection that can be explored, as seen in references listed on the original BDM project.
In the original project, that relies on Turing Machines, 1D and 2D binary arrays are supported, as well as 1D arrays with 4, 5, 6 and 9 discrete symbols. This extension keeps all these features working, while providing a Linear Bounded Automata mode that supports only 1D binary arrays - for now.
Along with the BDM implementation, is provided the C++ program developed for enumeration of Linear Bounded Automata and computation of distribution of generated strings. This can be used as base code for extending and experimenting the method for higher number of states, more alphabets, or for different models.
Visualization, comparison with Turing Machine BDM, and adjustment of generated distribution to the format used in the BDM package are also available.
Nivaldo is a neuroscience engineer looking to apply computer theory concept of algorithmic complexity to analyze neuronal response data of mices. He generates binary strings that codify time periods where neurons fire, and then use BDM with TM and LBA to have an estimation of the size of the underlying neural program, comparing both of the models results and connecting them with biological theories, feeling satistied with this new venue of research he can explore.
Alan is researching algorithm complexity and took a interesting in computing Linear Bounded Automata BDM with more alphabets and states. He verifies the enumeration program and policy, adjust it for its needs, computing more datasets for the project, further extending the package. He carefully studies the results with the help of the provided notebook, makes theoretical considerations, discussions, and happily publish them.
Harry wants to use the LBA enumeration tool. Unfortunately it cannot compile/run the program due to difficulties with the Windows environment he uses. He messages the maintainer of the project that responds acknowleding the trouble with the setup of the ltbb dependency in this Operating System, and recommends Harry to use a linux distribution through WSL (Windows Subsystem for Linux). Not happy, he looks for other tools before considering this.
Foster is interested in analyzing image complexity, and likes the idea of using pybdm-lba. He attempts running the Block Decomposition Method using LBA (Linear Bounded Automata) model and 2 dimensions and gets an error informing there is no such model available. Frustrated, he reviews the documentation and realizes 2 dimensional complexity is not implemented/supported with LBA, and resorts to using the TM (Turing Machine) model. He was able to study complexity of images that way, although not with the model he wanted.
You can use this package locally by cloning this repository:
git clone https://github.com/LexLoki/pybdm-lba.git
Adding the project directory to sys.path:
import os
import sys
module_path = os.path.abspath(r"PATH_TO_PYBDM_LBA") # or the path to your source code
sys.path.insert(0, module_path)Or you can simply use:
pip install git+https://github.com/LexLoki/pybdm-lba.git
Complete base usage is covered in the original (forked from) project and can be seen here
However, we cover the base usage with Turing Machines, for 1D sequences:
import numpy as np
from pybdm import BDM
# Create a dataset (must be of integer type)
X = np.ones((100,), dtype=int)
# Initialize BDM object
# ndim argument specifies dimensionality of BDM
bdm = BDM(ndim=1)
# Compute BDM
bdm.bdm(X)For LBA complexity, BDM object instantiation requires the parameter model='LBA' (that defaults to TM):
import numpy as np
from pybdm import BDM
# Create a dataset (must be of integer type)
X = np.ones((100,), dtype=int)
# Initialize BDM object
# ndim argument specifies dimensionality of BDM
bdm = BDM(ndim=1, model='LBA')
# Compute BDM
bdm.bdm(X)Note that we only provide implementation for 1D binary sequences. LBA dataset for 2D LBA models and with more symbols are potential future work to explore.
For full technical documentation on BDM, please refer to the original project documentation: https://pybdm-docs.readthedocs.io/en/latest/index.html
The original BDM project implemented a series of unit tests, using pytest, that are avaible at tests directory. We have added one extra test to account for our modification of the original project: test_bdm_lba_d1, in test_bdm.py, that verifies the correctess of complexity results when running BDM using binary one-dimensional Linear Bounded Automata.
- For full technical documentation on BDM, please refer to the original project documentation: https://pybdm-docs.readthedocs.io/en/latest/index.html
- For documentation on Linear Bounded Automata generation: https://github.com/LexLoki/pybdm-lba/wiki/Linear-Bounded-Automata-enumeration-program
- For documentation on analysis/visualization and dataset preparation: https://github.com/LexLoki/pybdm-lba/wiki/Visualization-and-dataset-preparation
- For technical discussion and thought process from the foundations of BDM to the details of the implementation of the enumeration tool, we wrote this article: https://mountain-eocursor-eb5.notion.site/Estimating-BDM-with-LBA-5bc261c301a648afab8839cd013c7734