Kolmogorov Complexity – A Primer (2012) • Hacker News Board

Kolmogorov Complexity – A Primer (2012)

#1

Post by poindontcare » Sun, Oct 02, 2016, 4:16 AM UTC

Kolmogorov Complexity – A Primer (2012)
jeremykun.com

Re: Kolmogorov Complexity – A Primer (2012)

#2

Post by cosmoharrigan » Sun, Oct 02, 2016, 8:06 AM UTC

Kolmogorov Complexity is also presented in Chapter 7 of the classic textbook "Elements of Information Theory": http://poincare.matf.bg.ac.rs/nastavno/viktor/Kolmogorov_Com...

Re: Kolmogorov Complexity – A Primer (2012)

#3

Post by cosmoharrigan » Sun, Oct 02, 2016, 8:13 AM UTC

An overview with additional references from Marcus Hutter: http://www.scholarpedia.org/article/Algorithmic_complexity

Re: Kolmogorov Complexity – A Primer (2012)

#4

Post by mherrmann » Sun, Oct 02, 2016, 8:13 AM UTC

When two strings have the same Kolmogorov Complexity, one of them might take significantly longer to "decompress". Shouldn't we then say that this string has higher information content?

It feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.

Re: Kolmogorov Complexity – A Primer (2012)

#5

Post by cosmoharrigan » Sun, Oct 02, 2016, 8:14 AM UTC

An extremely detailed treatment is presented in "An introduction to Kolmogorov complexity and its applications": http://www-2.dc.uba.ar/materias/azar/bibliografia/LiVitanyi1...

Re: Kolmogorov Complexity – A Primer (2012)

#6

Post by cosmoharrigan » Sun, Oct 02, 2016, 8:26 AM UTC

mherrmann wrote: post #4

When two strings have the same Kolmogorov Complexity, one of them might take significantly longer to "decompress". Shouldn't we then say that this string has higher information content? It feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.

See "Logical Depth" as defined by Charles Bennett: http://researcher.ibm.com/researcher/files/us-bennetc/UTMX.p... as well as Chapter 7, "Resource-Bounded Complexity", from "An introduction to Kolmogorov complexity and its applications".

Re: Kolmogorov Complexity – A Primer (2012)

#7

Post by mherrmann » Sun, Oct 02, 2016, 8:47 AM UTC

cosmoharrigan wrote: post #6

mherrmann wrote: post #4

When two strings have the same Kolmogorov Complexity, one of them might take significantly longer to "decompress". Shouldn't we then say that this string has higher information content? It feels to me like Kolmogorov Complexity (while very elegant) might just be a crude approximation to a measure that also takes into account the time it takes to print the string.

See "Logical Depth" as defined by Charles Bennett: http://researcher.ibm.com/researcher/files/us-bennetc/UTMX.p... as well as Chapter 7, "Resource-Bounded Complexity", from "An introduction to Kolmogorov complexity and its applications".

I'll take a look. Thanks!

Re: Kolmogorov Complexity – A Primer (2012)

#8

Post by s_q_b » Sun, Oct 02, 2016, 8:54 AM UTC

Boo, Wendy Testaburger. Boo Wendy.

.... But seriously, can we not all just learn higher math?

Re: Kolmogorov Complexity – A Primer (2012)

#9

Post by mherrmann » Sun, Oct 02, 2016, 9:02 AM UTC

s_q_b wrote: post #8

Boo, Wendy Testaburger. Boo Wendy. .... But seriously, can we not all just learn higher math?

I don't get it sorry. Care to explain for the non-Southpark buffs?

Re: Kolmogorov Complexity – A Primer (2012)

#10

Post by eveningcoffee » Sun, Oct 02, 2016, 9:13 AM UTC

Linux dev/random entropy quality check is (was, I have not checked it recently) based on Kolmogorov complexity.