Algorithmic Thermodynamics (Part 3)

This is my talk for the Santa Fe Institute workshop on Statistical Mechanics, Information Processing and Biology:

• Algorithmic thermodynamics.

It’s about the link between computation and entropy. I take the idea of a Turing machine for granted, but starting with that I explain recursive functions, the Church-Turing thesis, Kolomogorov complexity, the relation between Kolmogorov complexity and Shannon entropy, the uncomputability of Kolmogorov complexity, the ‘complexity barrier’, Levin’s co...