Skip to content

Kolmogorov Complexity – A Primer

jeremykun.com
4 pointssuioir1 comment
On HN

Comments

The proof of Lemma 1 says that a string of length n can be output by a program of length n+O(1) in any Turing complete programming language, but that ignores the fact that nearly all languages require certain characters in string literals to be escaped.

For this reason it is better to use languages that are custom designed for program size complexity, such as Binary Lambda Calculus [1].

[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.