本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：1997
摘要
We study 細胞自動機 where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to nonzero probability transitions in single spin-flip dynamics of the Ising模型 at zero temperature. We show that in three or more dimensions these systems can simulate Boolean circuits of AND and OR gates, and are therefore P-complete. That is, predicting their state t time-steps in the future is at least as hard as any other problem that takes polynomial time on a serial computer. Therefore, unless a widely believed conjecture in computer science is false, it is impossible even with parallel computation to predict majority-vote 細胞自動機, or zero-temperature single spin-flip Ising dynamics, qualitatively faster than by ex
※ 此為已發表論文，全文需透過期刊付費取得