acss_data: algorithmic complexity of short strings

Share:

Description

Contains the algorithmic complexity for short string, an approximation of the Kolmogorov Complexity of a short string using the coding theorem method. For a given set of symbols in a string, all possible or a large number of random samples of Turing machines (TM) with a given number of states and number of symbols corresponding to the number of symbols in the strings were simulated until they reached a halting state or failed to end. The complexity of the string corresponds to the distribution of the halting states of the TMs.

See http://complexitycalculator.com/methodology.html for more information or references below.

This dataset shouldn't be called directly but rather through the accessor functions in package acss.

Usage

1

Format

A data frame with 4590267 observations on the following 5 variables.

K.2

acss with 2 symbols, computed on all possible Turing machines (TM) with 5 states and 2 symbols.

K.4

acss with 4 symbols, computed on a large number of TMs with 4 states and 4 symbols.

K.5

acss with 5 symbols, computed on a large number of TMs with 4 states and 5 symbols.

K.6

acss with 6 symbols, computed on a large number of TMs with 4 states and 6 symbols.

K.9

acss with 9 symbols, computed on a large number of TMs with 4 states and 9 symbols.

Author(s)

Fernando Soler Toscano, Nicolas Gauvrit, and Hector Zenil.
Ported to R by Henrik Singmann.

Source

http://complexitycalculator.com/methodology.html

References

Delahaye, J.-P., & Zenil, H. (2012). Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness. Applied Mathematics and Computation, 219(1), 63-77. doi:10.1016/j.amc.2011.10.006

Gauvrit, N., Zenil, H., Delahaye, J.-P., & Soler-Toscano, F. (2014). Algorithmic complexity for short binary strings applied to psychology: a primer. Behavior Research Methods. doi:10.3758/s13428-013-0416-0

Soler-Toscano, F., Zenil, H., Delahaye, J.-P., & Gauvrit, N. (2012). Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines. arXiv:1211.1302 [cs.it].

http://algorithmicnature.org/

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.