I address two questions belonging to an interdisciplinary area between statistical mechanics and the theory of computation:

What is the proper measure of intrinsic complexity to apply to states of a physical system?

What role does thermodynamic irreversibility play in enabling systems to evolve spontaneously toward states of high complexity?