论文标题
计算可逆蜂窝自动机的Lyapunov指数
On computing the Lyapunov exponents of reversible cellular automata
论文作者
论文摘要
我们考虑计算可逆细胞自动机（CA）的Lyapunov指数的问题。我们表明，具有正确的Lyapunov指数$ 2 $的可逆CA类别不能与可逆的CA类别分开，其正确的Lyapunov指数最多为$ 2-δ$，对于某些绝对常数$δ> 0 $。因此，没有算法作为输入的说明，对任意可逆的CA $ F $和正理性数字$ε> 0 $的描述输出了$ f $的Lyapunov指数，并具有准确的$ε$。我们还计算了CA的平均Lyapunov指数（相对于统一度量），该指数在coprime $ p，q> 1 $的基本$ pq $中执行乘以$ p $。
We consider the problem of computing the Lyapunov exponents of reversible cellular automata (CA). We show that the class of reversible CA with right Lyapunov exponent $2$ cannot be separated algorithmically from the class of reversible CA whose right Lyapunov exponents are at most $2-δ$ for some absolute constant $δ>0$. Therefore there is no algorithm that, given as an input a description of an arbitrary reversible CA $F$ and a positive rational number $ε>0$, outputs the Lyapunov exponents of $F$ with accuracy $ε$. We also compute the average Lyapunov exponents (with respect to the uniform measure) of the CA that perform multiplication by $p$ in base $pq$ for coprime $p,q>1$.
