循环词

在数学中，循环词或序列是在有限字母上的一个无限词，其中每个因子都会出现无限多次。当且仅当一个无限的词是一个倍数时，它就是递归词。均匀递归词是一个递归词，其中对于序列中的任何给定因子X，有一些长度nX（通常比X的长度长很多），使得X出现在每个长度为nX的块中。也使用了最小序列和几乎周期性序列（Muchnik,Semenov,Ushakov2003）的术语。

制造一个循环序列的最简单的方法是形成一个周期性序列，一个序列在给定的m个步骤后完全重复。这样的序列是均匀递归的，nX可以被设置为m的任何倍数，大于X长度的两倍。Thue-Morse序列是均匀递归的，但不是周期性的，甚至不是最终周期性的（指在某些非周期性的初始段之后的周期性）。所有Sturmian词都是均匀递归的。