本題鏈接：

https://hdlbits.01xz.net/wiki/Rule110

Rule 110是一種一維單元格自動機(jī)，具有有趣的性質(zhì)（例如Turing-complete）。

有一個一維單元陣列（開或關(guān)）。在每個時間步，每個單元的狀態(tài)都會發(fā)生變化。在Rule 110中，根據(jù)下表，每個單元的下一個狀態(tài)僅取決于其自身及兩個相鄰單元：

（名稱“Rule 110”來自于讀取“next state”列：0110110是十進(jìn)制110。）

在這個電路中，創(chuàng)建一個512單元系統(tǒng)(q [511:0]) ，每個時鐘周期前進(jìn)一個時間步。load輸入表明系統(tǒng)的狀態(tài)應(yīng)該加載數(shù)據(jù)[511:0]。假設(shè)邊界(q [-1]和 q [512])都為零(關(guān))。

題目

提示:

當(dāng)初始狀態(tài)?q?[511:0]?=?1時，前幾次迭代是:

答案

輸出波形

規(guī)則110

在基本元胞自動機(jī)中，0 和 1 的一維模式根據(jù)一組簡單的規(guī)則演變。模式中的某個點在新一代中是 0 還是 1 取決于其當(dāng)前值以及其兩個相鄰值的值。

規(guī)則 110 自動機(jī)具有以下的規(guī)則：

“規(guī)則110”的名稱源于這樣一個事實，即該規(guī)則可以總結(jié)為二進(jìn)制序列01101110;這個二進(jìn)制數(shù)對應(yīng)于十進(jìn)制值是 110。

圖靈完備性

在可計算性理論，如果一系列操作數(shù)據(jù)的規(guī)則（如指令集、編程語言、細(xì)胞自動機(jī)）可以用來模擬任何圖靈機(jī)，那么它是圖靈完備的。這意味著這個系統(tǒng)也可以識別其他數(shù)據(jù)處理規(guī)則集，圖靈完備性被用作表達(dá)這種數(shù)據(jù)處理規(guī)則集的一種屬性。如今，幾乎所有編程語言都是具有圖靈完備性的。這個詞以引入圖靈機(jī)概念的數(shù)學(xué)家艾倫·圖靈命名。

一個計算系統(tǒng)可以計算任何圖靈-可計算函數(shù)，被稱作圖靈完全（或者圖靈完備）?；蛘呷魏慰梢阅M通用圖靈機(jī)的系統(tǒng)。

參考內(nèi)容：

?Rule_110?|?wikipedia：

https://en.wikipedia.org/wiki/Rule_110

Turing_completeness?|?wikipedia：

https://en.wikipedia.org/wiki/Turing_completeness