fa={{1,1}{1,0},{1,0}{2,1},{2,1}{2,1},{2,0}{1,0}};
fa
{{1,1}{1,0},{1,0}{2,1},{2,1}{2,1},{2,0}{1,0}}
{1,1}/.fa
{1,0}
{1,0,1,0,1,1,1,1,0,0}
{2,0}/.fa
{1,0}
NestList[f,x,5]
{x,f[x],f[f[x]],f[f[f[x]]],f[f[f[f[x]]]],f[f[f[f[f[x]]]]]}
(2+#)&[x^2]
2+
2
x
NestList[(1+#^2)&,x,4]
x,1+
2
x
,1+
2
(1+
2
x
)
,1+
2
(1+
2
(1+
2
x
)
)
,1+
2
1+
2
(1+
2
(1+
2
x
)
)


FoldList[f,x,{1,2,3,4}]
{x,f[x,1],f[f[x,1],2],f[f[f[x,1],2],3],f[f[f[f[x,1],2],3],4]}
FoldList[Plus,x,{1,2,3,4}]
{x,1+x,3+x,6+x,10+x}
FAApply[rule_,s0_,list_]:=FoldList[{First[#1],#2}/.rule&,{s0},list]
FAApply[fa,1,{1,0,0,1,1}]
{{1},{1,0},{2,1},{1,0},{1,0},{1,0}}
Rest[%]
{{1,0},{2,1},{1,0},{1,0},{1,0}}
Map[Last,%17]
{0,1,0,0,0}
Map[f,{1,2,3,4}]
{f[1],f[2],f[3],f[4]}
FAStep[rule_,s0_,list_]:=Map[Last,Rest[FoldList[{First[#1],#2}/.rule&,{s0},list]]]
FAStep[fa,1,{1,0,0,1,1}]
{0,1,0,0,0}
FAEvolveList[rule_,s0_,init_,t_]:=NestList[FAStep[rule,s0,#]&,init,t]
RasterGraphics[data_]:=Graphics[Raster[1-Reverse[data]],AspectRatioAutomatic]
RasterGraphics[data_,lab_]:=Graphics[Raster[1-Reverse[data]],AspectRatioAutomatic,PlotLabellab]
Table[0,{10}]
{0,0,0,0,0,0,0,0,0,0}
Show[RasterGraphics[FAEvolveList[fa,1,Table[0,{100}],300]]];
ToFARule[n_Integer,{s_Integer,k_Integer}]:=Flatten[MapIndexed[{1,-1}#2+{0,k}Mod[Quotient[#1,{k,1}],{s,k}]+{1,0}&,Partition[IntegerDigits[n,sk,sk],k],{2}]]
RasterGraphics[data_,lab_]:=Graphics[Raster[1-Reverse[data]],AspectRatioAutomatic,PlotLabellab]
Show[GraphicsArray[Partition[Table[RasterGraphics[FAEvolveList[ToFARule[i,{2,2}],1,Table[0,{40}],30],i],{i,0,255}],8]]];
Use a simple heuristic to find "interesting" cases: