Algorithmic Thermodynamics (Part 3)

 

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

• Computation and 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 computable version of complexity, and finally my work with Mike Stay on algorithmic thermodynamics.

In my talk slides I mention the ‘complexity barrier’, and state this theorem:

Theorem. Choose your favorite set of axioms for math. If it’s finite and consistent, there exists C ≥ 0, the complexity barrier, such that for no natural number n can you prove the Kolmogorov complexity of n exceeds C.

For a sketch of the proof of this result, go here:

• Chaitin’s incompleteness theorem.

In my talk I showed a movie related to this: an animated video created in 2009 using a program less than 4 kilobytes long that runs on a Windows XP machine:

For more

For more details, read our paper:

• John Baez and Mike Stay, Algorithmic thermodynamics, Math. Struct. Comp. Sci. 22 (2012), 771-787.

or these blog articles:

• Algorithmic thermodynamics (part 1).

• Algorithmic thermodynamics (part 2).

They all emphasize slightly different aspects!

This entry was posted on Tuesday, November 15th, 2016 at 11:33 pm and is filed under computer science, information and entropy. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to Algorithmic Thermodynamics (Part 3)

  1. Kram Einsnulldreizwei says:
    15 November, 2016 at 11:51 pm

    The link to the talk doesn’t seem to work. I get a 404 error.

    Reply
  2. domenico says:
    17 November, 2016 at 9:13 pm

    There are interesting theories, and articles.
    I wonder if it exist a numerical simulation of the a computation algorithmic thermodynamic with an ensemble of short Turing machines.
    I am thinking that some system, like the Ising model, have a two state string in a three dimensional structure (so that I understand the connection between string length and a function of volume, and the energy function like a step by step energy reduction in the time); so that if one consider some system like a calculus system (different from a Turing machine, but which it can be simulated by a Turing machine) then some systems can be a real algorithmic thermodynamics.

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

This site uses Akismet to reduce spam. Learn how your comment data is processed.