子串复杂度、平衡 01 串与 Sturmian 串
让我们先从两个小问题开始说起。第一个问题是,是否存在某个无限不循环的 01 串,使得对于任意一个正整数 n ,该 01 串中长度为 n 的子串都有且仅有 n + 1 种? 或许这个问题来得有些突然。让我们慢慢解释一下,这个问题是怎么来的。衡量一个 01 串的复杂程度有很多办法,比方说,我们可以去考察它的“子串复杂度”(subword complexity),即子串的种类有多丰富。我们用 pw(n) 来表示,在一个(有可能无限长的)数字串 w 当中,长度为 n 的子串一共有多少种。例如,对于无限 …