Grounding Occam's Razor in a Formal Theory of Simplicity

Everybody loves Occam's Razor, the heuristic often phrased as "When in doubt, choose the simplest option," and elegantly expressed by Albert Einstein via his maxim that theories should be "As simple as possible, but no simpler." This sort of advice sounds intuitively sensible, but without some precise understanding of what "simplicity" means, it's not particularly crisp guidance. My own interest in Occam's Razor arises largely from my work in artificial intelligence. A host of theorists have argued for Occam's central role in AI - going back to Ray Solomonoff in the late 1960s, whose theory of "Solomonoff induction" involves, essentially, AIs that understand the world via choosing the hypothesis represented by the shortest computer program [Sol64]. Marcus Hutter [Hut05] has built a rigorous theory of general intelligence under infinite or near-infinite computing resources, founded on this idea; and Eric Baum has argued the merits of similar ideas from a broad conceptual perspective [Bau04]. Occam's Razor has also been considered foundational in the philosophy of science, by many different thinkers [Gau03]. There is a lot of power in the idea that complex hypotheses, like the Ptolemaic epicycles, have been systematically cast aside in favor of simpler, more compact hypotheses like the Copernican model. However, all these applications of Occam's Razor either rely on very specialized formalizations of the "simplicity" concept (e.g.