ecaについて

ecaとは

ecaとは... wikiではあいまい回避で結構いろいろな定義がリストされるが、ここで話したいのは、elementary cellar automaton ... 一次元セルオートマトンのこと。

細かい話は、wikiを参照.。

セルオートマトンのプログラムを書いてみた。

#!/usr/bin/env python
class eca:
        def __init__(slf,rule,N):
                slf.rule=rule
                slf.N=N
                slf.i=0
                slf.status=[ [ 0 for i in range(slf.N)] for j in range(2)]

        def next_func(slf,l,s,r):
                d=int("%s%s%s" % (l,s,r),2)
                return (slf.rule >> d ) % 2

        def next_id(slf):
                if slf.i==0:return 1
                else:return 0

        def next(slf):
                s=slf.status[slf.i]
                t=slf.status[slf.next_id()]
                for i in range(slf.N):
                        t[i]=slf.next_func(s[i-1 % slf.N],s[i],s[(i+1) % slf.N])
                slf.i=slf.next_id()
                return slf.prnt()

        def prnt(slf):
                def char_prnt(c):
                        if c==1:return "+"
                        else:return " "
                return  "".join([char_prnt(i) for i in slf.status[slf.i] ])

        def set_status(slf,i,s):
                slf.status[slf.i][i]=s

        def get_status(slf,i):
                return slf.status[slf.i][i]

if __name__=="__main__":
        d=eca(110,50)
        d.set_status(25,1)
        for j in range(130): print d.next()

で、これだけでは面白くないので、深さ優先探索で一次セルオートマトンの逆に推移するプログラムを書いてみた。

#!/usr/bin/env python

import eca

class inverse_eca:
        def __init__(slf,rule,N):
                slf.rule=rule
                slf.N=N
                slf.i=0
                slf.status=[ [ 0 for i in range(slf.N)] for j in range(2)]
                slf.tlst=[[] for i in range(2)]
                for i in range(8):
                        slf.tlst[(slf.rule >> i) % 2].append("%03d" % int(format(i,'b')))

        def inverse_func(slf,s,k):
                tmp=[ i for i in slf.tlst[s] ]
                return [ [int(i[0]),int(i[2])] for i in tmp if int(i[1])==k]

        def next_id(slf):
                if slf.i==0:return 1
                else:return 0

        def next(slf):
                s=slf.status[slf.i]
                t=slf.status[slf.next_id()]
                tmp=[[0,1] for i in range(slf.N)]

                def recur_func(p_lst,i,k):
                        if not k in p_lst[i]:return False
                        idec,iinc= (i-1) % slf.N,(i+1) % slf.N
                        n_tset=slf.inverse_func(s[i],k)
                        for nt in n_tset:
                                if nt[0] in p_lst[idec] and nt[1] in p_lst[iinc]:
                                        if len(p_lst[i])==1 and len(p_lst[idec])==1 and len(p_lst[iinc])==1:
                                                return True
                                        save_idec  ,save_i   = p_lst[idec],p_lst[i]
                                        p_lst[idec],p_lst[i] = [nt[0]],[k]
                                        if recur_func(p_lst,iinc,nt[1]):
                                                return True
                                        p_lst[idec],p_lst[i] = save_idec,save_i
                        return False

                if not recur_func(tmp,0,0) and not recur_func(tmp,0,1):
                        print "Falt!!!! "
                        return slf.prnt()
                for i in range(slf.N):t[i]=tmp[i][0]

                slf.i=slf.next_id()
                return slf.prnt()

        def prnt(slf):
                def char_prnt(c):
                        if c==1:return "*"
                        else:return " "
                return  "".join([char_prnt(i) for i in slf.status[slf.i] ])

        def set_status(slf,i,s):
                slf.status[slf.i][i]=s

        def get_status(slf,i):
                return slf.status[slf.i][i]

        def set_statusstr(slf,str):
                i=0
                for s in str:
                        if s=='*':slf.status[slf.i][i]=1
                        else:slf.status[slf.i][i]=0
                        i+=1



if __name__=="__main__":

        rule=90
        N=50
        init_N=int(N/2)

        def trans(obj,tn):
                for i in range(tn):print "%2d,%s|" %(i,obj.next())
        def eca_copy(obj,obj2):
                for i in range(obj.N):obj2.set_status(i,obj.get_status(i))

        d=eca.eca(rule,N)
        e=inverse_eca(rule,N)

        d.set_status(init_N,1)
        print "%2d,%s|" %(0,d.prnt())
        trans(d,30)
        eca_copy(d,e)
        trans(e,5)

後者は、全体のセルの状態に対して非決定性オートマトンの実装にはなっていないので、推移先(通常のセルオートマトンにおいての推移元)の状態がなければ停止します。

覚書でした。