Critical Algorithmic Information Theory and the Asymptotic Emergence of Tsallis q-Exponentials in Formal Languages
Entropy · 23.10.2026 · 28 (11) · 1172
DOI: 10.3390/e28111172 ↗Kurz gefasst
Fachartikel in der Zeitschrift Entropy, online erschienen am 23.10.2026. Verfasst von Airton Deppman. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Conselho Nacional de Desenvolvimento Científico e Tecnológico, São Paulo Research Foundation, National Institute of Science and Technology for Nuclear Physics and Applications.
Abstract (Originalsprache)
We establish an asymptotically exact theoretical correspondence between the Solomonoff–Chaitin algorithmic semi-measure over formal derivation trees and Tsallis non-extensive statistical mechanics, uniquely characterized by a q-exponential distribution with q=5/3. Rather than assuming universal equivalence across arbitrary formal languages, we specify the explicit structural conditions required for this asymptotic emergence. We define the class of Binary-Choice Deterministic CNF Grammars (BCDGs) operating on a deterministic three-tape Turing machine MSISS. Under minimal optimal encoding where binary branching non-terminal nodes consume 1 bit and deterministic terminal leaf productions consume 0 bits, we prove that valid derivation parse trees of total size ℓ=2k+1 consume precisely |p$|=ℓ+12=k+1 bits (including a non-binary halting delimiter $∉{0,1}). Within the asymptotic grammar counting family N(ℓ)∼Cℓ−3/2μℓ, Kraft’s inequality imposes the strict structural bound μ≤2. At the critical phase transition point μ=2—where the topological entropy of the grammar Htop=log22=0.5bits/node exactly matches the asymptotic internal node density capacity of binary derivation trees—the exponential growth factor cancels identically against the tape density factor. This leaves the pure asymptotic power-law decay mAIT(ℓ)∼(2π)−1ℓ−3/2, which corresponds asymptotically to a Tsallis q-exponential distribution P(ℓ)∝eq(−λ(ℓ−ℓmin)) with q=5/3 and λ=32ℓmin. Furthermore, we prove that the truncated Shannon entropy of the derivation space is subextensive with respect to the scale cutoff L. The framework is fully validated through exact Catalan combinatorics and a verified numerical convergence script.
Förderung
- Conselho Nacional de Desenvolvimento Científico e Tecnológico
- São Paulo Research Foundation
- National Institute of Science and Technology for Nuclear Physics and Applications
Zitieren
APA
Deppman, A. (2026). Critical Algorithmic Information Theory and the Asymptotic Emergence of Tsallis q-Exponentials in Formal Languages. Entropy, 28(11), 1172. https://doi.org/10.3390/e28111172
Vancouver
Deppman A. Critical Algorithmic Information Theory and the Asymptotic Emergence of Tsallis q-Exponentials in Formal Languages. Entropy. 2026;28(11):1172. doi:10.3390/e28111172
BibTeX
@article{Deppman2026,
author = {Deppman, Airton},
title = {Critical Algorithmic Information Theory and the Asymptotic Emergence of Tsallis q-Exponentials in Formal Languages},
journal = {Entropy},
year = {2026},
volume = {28},
number = {11},
pages = {1172},
doi = {10.3390/e28111172}
}
EUVIMED