# reperiendi

## Phort Tiger

Posted in Uncategorized by Mike Stay on 2010 February 25

When I was seven, my parents gave me the frame of a clubhouse for my birthday; it had two walls and a roof. I and the neighborhood kids added the other walls; when someone down the street replaced the shingles on their roof, we took the discarded ones and shingled ours. We did half of it wrong before figuring out how shingles are supposed to go (start at the bottom!) Someone else found the remains of an alphabet used to put a surname on a mailbox. It was missing the letter “F”, so the clubhouse became “Phort Tiger”, anticipating the F -> PH meme by a decade and a half. We seceded from the union and declared our backyard to be the sovereign nation of Tigeria.

## Mechanistic creativity

Posted in Uncategorized by Mike Stay on 2010 February 25

Computers are better now at face recognition than humans. My brother Doug has written photoshop filters that can do a watercolor painting over a pencil sketch given a photo. And now, David Cope has produced really beautiful music from a computer; the genius of it is his grammatical analysis of music:

Again, Cope hit the books, hoping to discover research into what that something was. For hundreds of years, musicologists had analyzed the rules of composition at a superficial level. Yet few had explored the details of musical style; their descriptions of terms like “dynamic,” for example, were so vague as to be unprogrammable. So Cope developed his own types of musical phenomena to capture each composer’s tendencies — for instance, how often a series of notes shows up, or how a series may signal a change in key. He also classified chords, phrases and entire sections of a piece based on his own grammar of musical storytelling and tension and release: statement, preparation, extension, antecedent, consequent. The system is analogous to examining the way a piece of writing functions. For example, a word may be a noun in preparation for a verb, within a sentence meant to be a declarative statement, within a paragraph that’s a consequent near the conclusion of a piece.

This kind of endeavor is precisely what the science of teaching is about; if Cope can teach a computer to make beautiful music, he can teach me to make beautiful music. By abstracting away the particular notes and looking at what makes music Bach-like as opposed to Beethoven-like or Mozart-like, he has shown us where new innovation will occur: first, in exploring the space, and second, in adding new dimensions to that space.

## Algorithmic thermodynamics

Posted in Uncategorized by Mike Stay on 2010 February 22

John Baez and I just wrote a paper entitled “Algorithmic Thermodynamics.” Li and Vitányi coined this phrase for their study of the Kolmogorov complexity of physical microstates; in their model, given an encoding $x$ of a macrostate (a measurement of a set of observables of the system to some accuracy), the entropy $S(x)$ of the system is a sum of two parts, the algorithmic entropy $K(x)$ and the uncertainty entropy $H(x)$. The algorithmic entropy is roughly the length of the shortest program producing $x$, while the uncertainy is a measure of how many microstates there are that satisfy the description $x$. So roughly the microstates in their model are outputs of Turing machines.

In our model, microstates are inputs to Turing machines, specifically inputs that cause the machine to halt and give an output. Then we specify a macrostate using some observables of the program (computable functions from bit strings to real numbers, like the length, or runtime, or output of the program). Once we’ve specified the macrostate by giving the average values $\overline{C_i}$ of some observables $C_i,$ we can ask what distribution on microstates (halting programs) maximizes the entropy; this will be a Gibbs distribution

$\displaystyle p(x) = \frac{1}{Z} \exp\left(-\sum_i \beta_i C_i(x)\right),$

where

$\displaystyle Z = \sum_{x \in X} \exp\left(-\sum_i \beta_i C_i(x)\right)$

and

$\displaystyle -\frac{\partial}{\partial \beta_i} \ln Z = \overline{C_i}.$

The entropy of this system is

$\displaystyle S(p) = -\sum_{x \in X} p(x) \ln p(x);$

from this formula we can derive definitions of the conjugates of the observables, just like in statistical mechanics.

If we pick some observable $C_j$—say, the runtime of the program—to play the role of the energy $E,$ then its conjugate $\beta_j$ plays the role of inverse temperature $1/T:$

$\displaystyle \frac{1}{T} = \left.\frac{\partial S}{\partial E}\right|_{C_{i \ne j}}.$

Given observables to play the roles of volume and number of particles—say, the length and output, respectively—we can similarly define analogs of pressure and chemical potential. Given these, we can think about thermodynamic cycles like those that power heat engines, or study the analogs to Maxwell’s relations, or study chemical reactions–all referring to programs instead of pistons.

And since the observables are arbitrary computable functions of the program bit string, we can actually recover Li and Vitányi’s meaning for ‘algorithmic thermodynamics’ by interpreting the output as a description of a physical macrostate; so our use of the term includes theirs as a special case.

## Tutorial on how to overlay tiles on Google maps

Posted in Uncategorized by Mike Stay on 2010 February 21