A High-Low Kolmogorov Complexity Law equivalent to the 0–1 Law
Marius Zimand · Information Processing Letters · 1996
It is shown that the 0–1 Law for recursive logics on finite structures admits an equivalent formulation in terms of Kolmogorov complexity. The new formulation opens the possibility of using the Kolmogorov complexity apparatus to easily derive various properties for finite structures satisfying a given properties. Examples that illustrate this point are provided.