title: Algorithmic complexity for short binary strings applied to psychology: a primer.
abstract: As human randomness production has come to be more closely studied and used to assess executive functions (especially inhibition), many normative measures for assessing the degree to which a sequence is randomlike have been suggested. However, each of these measures focuses on one feature of randomness, leading researchers to have to use multiple measures. Although algorithmic complexity has been suggested as a means for overcoming this inconvenience, it has never been used, because standard Kolmogorov complexity is inapplicable to short strings (e.g., of length l ≤ 50), due to both computational and theoretical limitations. Here, we describe a novel technique (the coding theorem method) based on the calculation of a universal distribution, which yields an objective and universal measure of algorithmic complexity for short strings that approximates Kolmogorov-Chaitin complexity.
authors: CHART (PARIS-reasoning), University of Paris VIII and EPHE, Paris, France, ngauvrit@me.com.
authors: Nicolas
authors: N
authors: Gauvrit
authors: Hector
authors: H
authors: Zenil
authors: Jean-Paul
authors: JP
authors: Delahaye
authors: Fernando
authors: F
authors: Soler-Toscano
mesh_terms: D000465:Algorithms; D001331:Automation; D001519:Behavior / Q000502:physiology*; D002648:Child; D003071:Cognition; D003198:Computer Simulation; D056344:Executive Function; D005260:Female; D006801:Humans; D007802:Language; D008297:Male; D008570:Memory, Short-Term; D008962:Models, Theoretical; D009483:Neuropsychological Tests; D011336:Probability; D011584:Psychology / Q000379:methods*