線性細(xì)胞自動機(jī)的可逆性研究.pdf

1、細(xì)胞自動機(jī)(Cellular Automata)是離散的和確定性的動態(tài)系統(tǒng)，它們尤其適合用于建模與仿真，可以被描述為簡單的對象彼此局部相互作用的龐大集合的自然系統(tǒng)。近幾年來，細(xì)胞自動機(jī)已經(jīng)廣泛應(yīng)用在科學(xué)的各個分支，如物理學(xué)(生長過程模型）、生物學(xué)(自我繁殖模型、生物結(jié)構(gòu)等）、信息科學(xué)(圖像處理、糾錯碼、密碼學(xué)等）。
　　在一維細(xì)胞自動機(jī)方面，目前在零邊界、反射邊界和周期邊界條件下，一維線性細(xì)胞自動機(jī)的可逆性已經(jīng)取得了一些成果，但是

2、許多已有研究工作都是針對特定的某些線性規(guī)則，難以做到判定任意線性規(guī)則的可逆性。本文創(chuàng)新性地引入De Bruijn圖這一強(qiáng)大工具，可以在零邊界條件下快速確定任意一維線性細(xì)胞自動機(jī)的可逆性，并且可以推廣到有限狀態(tài)域Fp上。
　　在二維細(xì)胞自動機(jī)方面，Kari等人證明了二維或高維細(xì)胞自動機(jī)在全局的可逆性是不可判定問題。本文探究了零邊界條件下二維線性細(xì)胞自動機(jī)的可逆性，通過實(shí)驗(yàn)給出了整體可逆的二維線性CA和整體不可逆的二維線性CA所需要滿