本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1160
- 日期：2026-03-18
摘要
我們證明，如果二維或更多維度的元胞自動機支持不斷增長的“梯子”，這些“梯子”可以相互轉動或阻擋，那麼它就可以表達任意布爾電路。那麼，在有限時間內預測 CA 的問題就變成了 P-完全問題，有限配置是否增長到無窮大的問題就變成了 P-困難問題，並且具有周期性背景的初始條件的長期行為是不可判定的。此類包括「沒有死亡的生命」規則，其中，如果恰好有三個相鄰單元處於打開狀態，則單元將打開，並且永遠不會關閉。