The approach I've long thought would bear fruit turns out to be a dumbed-down version of Aaronson's. Imagine a "meta-sequence" whose elements are features of t

The approach I've long thought would bear fruit turns out to be a dumbed-down version of Aaronson's. Imagine a "meta-sequence" whose elements are features of the original sequence in question, then take the entropy of the meta-sequence. Different features yield different kinds of "interestingness". For example, you could form your meta-sequence with a histogram of the original sequence. Original: A B A A B B A B Meta: 4 4 (4 As, 4 Bs) Entropy of the meta sequence is low. But instead of just looking at the values of the PMF or PDF, you might want to look at things like transition probabilities between different elements in the original sequence to capture the fact that A A A A B B B B and A B A B A B A B have more boring transition probabilities than A A B A B A B B And so on; one can imagine having an ever-more-sophisticated array of features to look for when forming the meta-sequence. But Kolmogorov complexity seems to cut more directly to the heart of the matter. If I'm specifically looking for something computationally feasible, maybe I would do a weighted sum of the entropies of k-order transition matrices, from k=1 to some limit.