Complexity function: Difference between revisions

Revision as of 12:20, 23 February 2014

Revision as of 12:25, 23 February 2014

Line 23:

:<math>H_{\mathrm{top}}(u) = \lim_{n \rightarrow \infty} \frac{\log p_u(n)}{n \log k} \ . </math>

The limit exists as the logarithm of the complexity function is [[Subadditivity|subadditive]].<ref name=PF4>Pytheas Fogg (2002) p.4</ref><ref name=AS303>Allouche & Shallit (2003) p.303</ref> Every real number between 0 and 1 occurs as the topological entry of some sequence.,<ref name=CN169>Cassaigne & Nicolas (2010) p.169</ref> which may be taken to be [[Uniformly recurrent word|uniformly recurrent]] or even uniquely ergodic.<ref name=BR169>Berthé & Rigo (2010) p.169</ref>

For ''x'' a real number and ''b'' an integer ≥ 2 then the complexity function of ''x'' in base ''b'' is the complexity function ''p''(''x'',''b'',''n'') of the sequence of digits of ''x'' written in base ''b''.