We know the 2-symbol 2-state BB. We can guess O(log 3) bits of new information. But we don’t know the 3-symbol 3-state BB. What’s the catch?

]]>I’ve since heard from others that he’s known for this sort of thing. I still feel bad about it, since before this incident, I’d liked Chaitin and had had some great conversations with him.

The real irony is that, far from “dismissing” his work, I’d actually found it the most interesting thing at that workshop—although I’d probably tone down the claims he made for its world-changing importance to biology by at least 4 orders of magnitude. š

Briefly, Chaitin studies a model of evolution for which the word “idealized” is an understatement—which is actually fine by me! He has a population of exactly one organism, “mutations” that can be arbitrary computable maps and that never make things worse—oh, and a fixed fitness function that requires an oracle for the halting problem in order to evaluate it. The question that interests him is whether “mutation”—or I’d simply call it randomized hill-climbing—can discover “genuinely new information,” which in his mind, can only mean learning additional bits of Chaitin’s constant Ω. š

I.e., if you told him that the evolution that takes a bacterium to a cheetah was governed solely by computable processes (even huge ones taking billions of years), then unless I badly misunderstood, he’d say that that evolution was ipso facto uninteresting: the only evolution that matters for him is the kind that has some uncomputable aspect.

Setting aside any qualms we might have about that, his main result is that, yes, a suitably-defined randomized hill-climbing process can keep discovering additional bits of Ω, provided (again) that we have a HALT oracle with which to compute the fitness function.

At a technical level, his result boils down to the following observation, which while simple was completely new to me. If you define Busy Beavers using a suitable programming language (say, a prefix-free one), and you know the n^{th} Busy Beaver, then someone can let you compute the (n+1)^{st} Busy Beaver by giving you only O(log n) bits of new information. So in particular, if you randomly guessed the additional information (and then verified it with your HALT oracle), you’d have a 1/poly(n) probability of getting it right, and thereby “improving your fitness”—that is, learning a new Busy Beaver number, and correspondingly one or more new bits of Ω.

I’ll let you decide for yourself whether this is biology or vaguely-biologically-inspired computability theory. š

Anyway, as far as I can see, my result “relates” to his only insofar as they both involve both *math* and *biology*! Besides that, they’ve got nothing to do with each other—for starters, mine says nothing about evolution, while his says nothing about DNA.

For 1≤k≤4, where 2k/3e<1, I’m guessing 2^n is the largest you know how to get?

]]>OK, but if you can specify each S uniquely using n bits, then there are at most 2^n possible Sās.

I guess that’s one way of saying “Since there are at most 2^n possible S, there are at most 2^n possible S.” š

]]>First, there exist DNA strings for which the “utopian string” is reachable, but is *not* reachable by applying all n recombinases in an irreducible order. As an example:

A ( B [ C { D [ E { F ( G.

This has AG as its utopian string. But on the way to AG, if the [-recombinase acts then the { one can’t act, and vice versa.

Second, something weaker is true: namely, whenever the utopian string is reachable, it’s reachable by applying all n recombinases in *some* order. To see this: clearly the utopian string must be reachable by applying *some* subset S of the recombinases in an irreducible order. Now suppose that after we do that, there are still matching pairs of recognition sites left in the DNA string. Then there are letter-chunks that are currently next to each other, but could be moved away from each other (or switched in their relative orientations) by further recombinase applications. Hence some letter-chunks were *not* paired off with their soulmates, so the string was not utopian, contrary to assumption. It follows that we can now apply all the remaining recombinases (the ones not in S), without any of them taking us away from the utopian string.