摘要 我們證明了各種各樣的非線性元胞自動機（CA）可以分解為線性元胞自動機的準直積

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2022-09-02

摘要

我們證明了各種各樣的非線性元胞自動機（CA）可以分解為線性元胞自動機的準直積。這些 CA 可以透過使用具有二進位輸入的閘的深度為 0(log(2)t) 的平行電路來預測，或者如果允許具有無限數量輸入的「sum mod p」閘，則可以預測深度為 0(log t) 的平行電路。因此，這些 CA 可以透過（理想化的）平行計算機比透過顯式模擬更快地預測，即使它們是非線性的。此類別包括任何 CA，其規則在寫為代數時是可解群。我們還表明，基於冪零群的 CA 可以分別透過具有二進位或「sum mod p」閘的電路在深度 0(log t) 或 0(1) 上進行預測。我們使用這些技術為 CA 規則提供了一種有效的演算法，該規則與基本 CA 規則 Is 一樣，具有成對消除的擴散缺陷。這可用來預測規則 18 中缺陷在 0(log(2) t) 並行時間內的移動。