The n-Category Café

Quoting from the paper:

“Charles Babbage described a computer powered by a steam engine; we describe a heat engine powered by programs! We admit that the significance of this line of thinking remains a bit mysterious. However, we hope it points the way toward a further synthesis of algorithmic information theory and thermodynamics. We call this hoped-for synthesis ‘algorithmic thermodynamics’.”

Though programs can be appreciated abstractly, I think people lose sight of the physical implementation of a program = unfolding of an stored electro-magnetic configuration on a hard drive. I think it was Bennett who said that a computable operation was no longer reversible after a release of heat had occurred.

This reminded of the other paper you guys collaborated on, something like: Does the HUP imply Godelian Incompleteness?

Hi,

I haven’t read the paper yet, but while I have a passing moment here, I hope to quickly relate this to a recent challenge I posed in a series of articles:

• The Ultimate Wireless Broadband Speed Limit
• Hello Heisenberg
• Physics of Wireless Broadband

Information is physical and the ability to transmit wireless information is related to the ability to transmit electromagnetic waves. It would be interesting to study information theory in relation to electromagnetic theory.

Times up…

Nice paper!

When talking about “programs”, you do not distinguish executable code and data - it is custom not to make this distinction in the present context, but maybe some of your readers will be thankful if you explain this in the introducton :-)

A prefix-free Turing machine is one whose halting programs form a prefix-free set.

There is something here that I don’t get: If the machine halts if fed with a program X, it is supposed not to halt for every other program that starts with X?
(That sounds strange to me, maybe it’s easier for me to think of equivalence classes of programs instead, I’ll try that).

Some misprints:

p.8, double “the”: We use μ/T to stand for the the conjugate variable of N.

p.10, verb should denote plural: Then simple calculations, familiar from statistical mechanics [17], shows…

p.10, missing “to” in “useful to think”: To build intuition, it is useful think of the entropy S

p.10: One “the” too much: The algorithmic temperature, T , is the roughly the number of

[John Baez: Thanks for all the corrections! For some reason I’m not being allowed to post comments. Until this gets fixed, I will have to manifest myself as ‘the ghost in the machine’.

You write:

When talking about “programs”, you do not distinguish executable code and data…

Yeah, sorry. Our way of speaking would probably be understood as convenient slang among people who work on algorithmic information theory. But since we’re hoping to expand our audience beyond those folks, we should be clearer.

If everyone blogged about their papers before publishing them, everyone would see how many obstacles to understanding their papers contain!

There is something here that I don’t get: If the machine halts if fed with a program X, it is supposed not to halt for every other program that starts with X?

The issue of ‘halting’ is not really the main point here. The key idea is that a program should not contain another as an initial segment. So intuitively, just imagine that every program must end with a string that says

THE END

written out in binary.

As explained in the quote by Mike here, this is just a convenient trick for making

∑_X 2^-|X|

converge when we sum over all programs X. This let us define a probability measure on programs — or more precisely, on the set of things we’re allowed to feed our universal Turing machine! That’s very convenient.

Mike’s thesis attributes this trick to Chaitin, while the Wikipedia article says “There are several variants of Kolmogorov complexity or algorithmic information; the most widely used one is based on self-delimiting programs and is mainly due to Leonid Levin (1974).”]

When you show the two strings above and say that the uppermost has more algorithmic entropy, my first thought is that this is just a new name for kolmogorov complexity, an impression that sticks with me for a while as I’m reading. On page 6 you make the connection to kolmogorov (algorithmic information) but I wonder if it wouldn’t have been more intuitive to some, if kolmogorov was there from page 1.

This is the problem with uniting ideas in different fields I guess. What’s “intuitive” depends on your vantage point :-)

[John Baez: For some reason I’m not being allowed to post comments. But I can still edit other people’s comments. So, I’ll manifest myself in this unconventional way. Sorry.

You’re right: ‘Algorithmic entropy’ is almost the same as ‘Kolmogorov complexity’, and we should mention this.

The phrases ‘descriptive complexity’, ‘Kolmogorov-Chaitin complexity’, ‘Solomonoff-Kolmogorov-Chaitin complexity’, ‘stochastic complexity’, and ‘program-size complexity’ are other near-synonyms. Unfortunately, I don’t think everyone agrees on what all these terms mean! And in our work the details matter. Mike’s thesis summarizes the story:

In the mid-1960’s, Kolmogorov, Solomonoff, and Chaitin independently proposed the idea of using programs to describe the complexity of strings. This gave birth to the field of algorithmic information theory (AIT). The Kolmogorov complexity KU(s) of a string s is the length of the shortest program in the programming language U whose output is s. Solomonoff proposed a weighted sum over the programs, but it was dominated by the shortest program, so his approach and Kolmogorov’s are roughly equivalent. Chaitin added the restriction that the programs themselves must be codewords in an instantaneous code, giving rise to prefix-free AIT. In this model, complexities become true probabilities, and Shannon’s information theory applies directly.

In our paper, we fix a universal prefix-free Turing machine, and define the algorithmic entropy of a natural number s to be

- ln(∑_x 2^-|x|)

Here we are summing over all bit strings x that give n as output, and we use |x| to mean the length of the bit string x.

If one program x having n as output is a lot shorter than all the rest, then the algorithmic entropy of n is about (ln2) |x|. And in this case its Kolmogorov complexity is just |x|.

More generally, the Kolmogoriv complexity is always just |x|, and there’s a bound on the difference between the Kolmogorov complexity and the algorithmic entropy divided by ln2. The ln2 is no big deal: it shows up merely because physicists prefer natural logarithms, while computer scientists prefer base 2.

To make the above ideas precise, let me define the concept of a ‘universal prefix-free Turing machine’. This idea plays a basic role in modern algorithmic information theory.

Let me use string to mean a bit string, that is, a finite, possibly empty, list of 0’s and 1’s. If x and y are strings, let xy be the concatenation of x and y. A prefix of a string z is a substring beginning with the first letter, that is, a string x such that z = xy for some y.

A prefix-free set of strings is one in which no element is a prefix of any other. The domain dom(M) of a Turing machine M is the set of strings that cause M to eventually halt. We call the strings in dom(M) programs. We assume that when the M halts on the program x, it outputs a natural number M(x). Thus we may think of the machine M as giving a function M from dom(M) to the natural numbers.

A prefix-free Turing machine is one whose halting programs form a prefix-free set. A prefix-free machine U is universal if for any prefix-free Turing machine M there exists a constant c such that for each string x, there exists a string y with

U(y) = M(x)

and

|y| ≤ |x| + c.

This gobbledygook says that U can simulate M.

All this stuff and more is in our paper!

Challenge for category theorists: create a category where a ‘universal’ Turing machine actually has some universal property. If the Turing machine M can simulate the Turing machine N, we should have a morphism from M to N. Then a universal Turing machine should be something like a weak initial object: it has a morphism, not necessarily unique, to every other Turing machine.]

1. I think the term “cross-entropy” is much better established than “relative entropy”. (Let’s pass over “Kullback-Leibler distance”.)

2. Would it be meaningful to ask what a phase transition means, on the algorithmic side?

[John Baez: Sorry, I’ll have to reply this way.

1. Cross-entropy may be more commonly discussed than relative entropy, but unfortunately it means something else. Given probability measures p and q on a countable set X, the cross-entropy of p with respect to q is:

-∑_x p(x) ln(q(x))

while the relative entropy of p with respect to q is:

-∑_x p(x) ln(p(x)/q(x))

They’re closely related: the relative entropy of p with respect to q is the cross-entropy of p with respect to q minus the entropy of p. I like relative entropy better because I know how to define it for any pair of probability measures p and q on a measure space:

-∫_X ln(dp/dq) dp

as long as p is absolutely continuous with respect to q, so the Radon-Nikodym derivative dp/dq is well-defined.

But some good may come of all this terminological nonsense: maybe some of our formulas would simplify if we used cross-entropy.

2. I’m definitely interested in finding and studying critical points in algorithmic thermodynamics. Manin did something similar in the papers Zoran mentioned here. Unfortunately Manin’s functions are all uncomputable! Our partition function is computable except in the T → ∞ limit: the ‘high-temperature limit’, where programs with long runtimes count a lot so the halting problem kicks in. I would love to extract interesting information from studying the behavior of the partition function as T → ∞, but we haven’t figured out how yet.]

Some ideas on connections between computation/information and statistical physics/thermodynamics are contained in 3 recent papers of Yuri Manin

* Yuri Manin, Renormalization and computation I: motivation and background, arxiv 0904.4921, Renormalization and Computation II: Time Cut-off and the Halting Problem arxiv 0908.3430

* Yuri Manin, Matilde Marcolli, Error-correcting codes and phase transitions, arxiv 0910.5135

I was wandering what you get when you restict the possible programs to cellular automata: Programs that change pieces of data only according to “neighbour” data.

Gerard

Do you find analogues to all the usual laws of thermodynamics? I wonder what the equivalent of a perpetual motion machine would be.

Thank you for writing this article as I am bent on penetrating what has been written in A NEW KIND OF SCIENCE by Stephen Wolfram.

While I appreciate the use of formulas here as well as at this link as a way to comprehend what Wolfram writes, I also would note that this author claims: “Above 1D no systematic method seems to exist for finding exact formulas for entropies” (p.959) and “So the fact that traditional science and mathematics tends to concentrate on equations that operate like constraints provides yet another reason for their failure to identify the fundamental phenomenon of complexity that I discuss in this book.” (p.221)

For the 1D cellular automata, Wolfram suggests the closest analog to be Limit[Sum[UnitStep[p[i]], {i,k^n}]/n, n → ∞]

Do you recognize this notation or does a 1D entropy not apply significantly when using formulas such as the one you write about?

I carefully read the paper many times and would just ask these two questions:

1. What’s the difference in your mind between the # of programs which can be doubled in Algorithmic Temperature and the Mean Length of the programs? It seems as if the length of a program is relative to the number of programs on initial conditions.

2. Why does Tadaki categorize your algorithmic pressure as his algorithmic temperature (or why do you elect to discuss algorithmic temperature as something that he calls pressure?) Does it make little difference?

In Wolfram’s NKS he shows mechanical work is possible due to the orderly cyclical repetitions of his 2 dimensional CA as long as no object is present to distract the simple repetitions. (p.446)

Also, I have to ask because it is starting to bug me.

How do you know there are two relative probability measures (p,q)? Since it is one dimensional, is it even possible to use the relative part of the equation? Maybe there is only one variable for information to be learned?

Interesting Idea. But I think a better name should be “Thermodynamic Algorithms”?

The fact that the energy (and the other variables, for that matter) is entirely arbitrary makes me rather leery of any strong connection to thermodynamics. Saying instead “statistical mechanics” alleviates some of this, as that truly is maximization of Shannon entropy relative to some prior measure, consistent with observed constraints.

The first question that springs to my mind is: “what are reasons to consider particular constraints as useful?”. Physically, there are certain macroscopic variables we care about, and the ones you pick are ones we do tend to care about in CS. The second is: “what are good priors to consider?” In physics, of course conservation of phase-space volume gives us that prior, but anything analogous is much harder to think about without some notion of time to give us conserved quantities.

I haven’t yet read the paper, but I prefer a two column text layout, as opposed to one column with 2 inch margins on each side.

A revised version of our paper on algorithmic thermodynamics is now available on the arXiv, and I’ve written an introduction to it here.