We provide a rigorous first-principle derivation of the non-additive Tsallis' entropy by employing the Chaitin-Kolmogorov algorithmic information theory. By applying non-local restrictive rules on the string formation (grammar), we show that the algorithmic cost follows a power-law of the string length, instead of the linear behaviour obtained in the classical theory. As a result, the Tsallis entropy governs the increase of information. We explore the result showing, through Landauer's limit, that the heat dissipation in systems with long-range correlations is diminished. The $Ω_q$ number, which remains incompressible, now offers the possibility of a continuous increase of complexity, measured by the parameter $q$. We show the consistency of the results by a numerical simulation, and discuss Zipf's law in light of the new findings.