具有位切換的規則 30 自動機的最小循環長度
規則 30 元胞自動機從一個非常簡單的規則產生混沌輸出，因此可以用作偽隨機生成器（但不是密碼安全的生成器）。
問題之一是存在“黑洞”，例如常量 0 位向量被映射到自身，而常量 1 向量被映射到常量 0。
這可以使用位 0（最右邊的位）的簡單切換（通過 XOR）來修復；這是一個簡單的實現
C。問題。“Rule 30 with bit toggle”的最小周期長度是否為 $ {\cal O}(2^n) $ 在哪裡 $ n $ 是位向量的長度？
使用參考實現中的約定，遞歸是 $$ u_{j+1}:=c\oplus(u_j\lll1)\oplus(u_j\vee(u_j\ggg1)) $$ 在哪裡 $ c $ 是個 $ n $ -位常數，所有位為 $ 0 $ 除了最右邊（否則說 $ c=0^{n-1}\mathbin|1 $ ), $ \oplus $ 是按位異或， $ \vee $ 是按位或， $ \lll $ 和 $ \ggg $ 是左右旋轉 $ n $ -bit 運算符之前的位雙字元串之後的位數。
如果我們反轉移位的方向，那隻會反映（循環）位映射，因此不會改變循環結構。
“Rule 30 with bit toggle”的最小周期長度是否為 $ {\cal O}(2^n) $ 在哪裡 $ n $ 是位向量的長度？
不，因為奇數 $ n $ 有一個長度為 1 的最小循環。該不動點具有二進製表達式 $ \frac{n+1}2\ 1 $ 和 $ \frac{n-1}2\ 0 $ （十六進制：
55…55對於 $ n\bmod 4=3 $ 或15…55為 $ n\bmod 4=1 $ ）。因此，在下文中，我們限制甚至 $ n $ .探索小 $ n $ 沒有證據表明該主張：最小周期長度通常為 $ 3 $ ，而且似乎沒有暴漲。
n length start 2 2 0x0 4 5 0x1 6 3 0x03 8 6 0x14 10 3 0x07C 12 5 0x42F 14 7 0x035D 16 33 0x2D34 18 3 0x03E43 20 27 0x00A28 22 3 0x07C87C 24 4 0x102040 26 14 0x0ABB343 28 5 0x2D1E5A3 30 3 0x03E43E43 32 7 0x1B3AFA05 34 3 0x07C87C87C 36 13 0x0217F5A73對於隨機函式，從隨機點開始的循環的預期大小接近 $ \sqrt{\pi2^n/8}=\mathcal O(2^{n/2}) $ ; 請參閱 Flajolet&Odlyzko 的隨機映射統計。最小的周期通常要小得多（儘管我不知道預期的分佈）。因此，聲稱的周期長度會有點令人驚訝。
另一方面，該函式具有非常緩慢的擴散，因此與隨機函式相距甚遠。
這是一個圖表 $ n=14 $ .
