On the High Information Content of a Class of Objects with Low Algorithmic Complexity

Adrian German

Indiana University-Bloomington

A simple Mealy machine with three states is responsible for multiplication by 2 in balanced ternary. In the limit, starting with 2^0 and repeatedly applying the Mealy machine to its own outputs, the machine (although completely deterministic) behaves as a stationary Markov chain with a uniform distribution—a fact that can be noticed early (after only 10,000 iterations). The immediate consequence is that the strings of trits representing powers of 2 in ternary balanced are in the limit: (a) computationally irreducible, and (b) normal in the Borel sense. For, despite having low Chaitin complexity, the strings generated have a lower bound on the coefficient of compression (over all possible codes) rapidly converging to 1. A brief discussion ends the paper, on how NKS might mitigate the relationship between algorithmic information theory (AIT) (Chaitin) and the classical information theory (Shannon) by offering a finer scale on which complexity could and perhaps should be measured.

[presentation materials]