Physics and Computation

2009

September 7-11th 2009

Ponta-Delgada, Azores, Portugal

## Main.KohtaroTadaki History

Hide minor edits - Show changes to output

August 03, 2009, at 11:04 AM
by

- Changed lines 34-35 from:

Furthermore, we show that this situation holds for the

to:

Furthermore, we show that this situation holds for the

August 03, 2009, at 11:04 AM
by

- Deleted line 0:

Changed lines 20-21 from:

In this talk, we develop a statistical mechanical interpretation

to:

In this talk, we develop a statistical mechanical interpretation

August 03, 2009, at 11:04 AM
by

- Added lines 1-45:

!! Talk from Kohtaro Tadaki

!!! Title

A statistical mechanical interpretation of algorithmic

information theory

!!! Abstract

Algorithmic information theory (AIT, for short) is a framework to

apply information-theoretic and probabilistic ideas to recursive

function theory. One of the primary concepts of AIT is the

program-size complexity H(s) of a finite binary string s, which is

defined as the size of the shortest program for a universal

decoding algorithm U to output s. By the definition, H(s) can be

regarded as the size of the optimal compression of a finite binary

string s. Furthermore, the notion of program-size complexity

enables us to consider the notion of compression rate for an

infinite binary string, or equivalently, a real.

In this talk, we develop a statistical mechanical interpretation

of AIT by introducing the notion of thermodynamic quantities at

temperature T, such as partition function Z(T), free energy F(T),

energy E(T), and statistical mechanical entropy S(T), into AIT.

These quantities are real functions of a real argument T > 0, and

are defined using all programs of U based on the identifications of

programs of U with energy eigenstates in statistical mechanics and

of the length of the programs with the energy of the energy

eigenstates. We investigate the properties of these quantities by

means of program-size complexity from the point of view of AIT.

It is then discovered that, in the interpretation, the temperature

T equals to the compression rate of the values of all these

thermodynamic quantities if T is a computable real in (0,1).

Furthermore, we show that this situation holds for the

temperature T itself as a thermodynamic quantity. Namely, we

show that, for every T in (0,1), if the value of partition function

Z(T) is computable, then the compression rate of T equals to T

itself. Thus, the computability of the value of partition function

Z(T) gives a sufficient condition for T in (0,1) to be a fixed point

on compression rate. In addition, we show that the computability

of each of the thermodynamic quantities F(T), E(T), and S(T) also

gives the sufficient condition. Moreover, based on the statistical

mechanical relation F(T) = - T \log_2 Z(T), we show that the

computability of F(T) gives completely different fixed points from

the computability of Z(T), in particular.