Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas -- Reversible CAs
		(a.) one dimension	- 2 colors

ReversibleQ[] tests 1-d CAs for reversible rules (see: NKS (2002) on page 1017).
InvertRR[]     reports the "invert rule" rulenumber, color k and range r
                   
Consider the (256)  basic 2-color rules.

rr2color=Fold[If[ReversibleQ[#2], Append[#1,#2],#1]&,{},Range[0,255]]

InvertRR[15]

Table[{rr2color[[j]], InvertRR[rr2color[[j]]]//First},{j,6}]//MatrixForm

Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas 
		(a.) one dimension	- 2 colors

DemoRR[240,NSteps->30]

Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas 
		(a.) one dimension	- 3 colors

NKS (2002) states that there are 1800 reversible rules (out of the possible 7625597484986 rules)  
                      for the k=3, r=1;   
 My student found about 100 of these ...

(*sr = <<"sahand/2006aug04\\Reversible3Rules_2.m";*)
(*see  http://forum.wolframscience.com/showthread.php?s=&threadid=1403*)
sr=Join[Table[{277206003607,{3943740214583,3,1}},{8}],Table[{409094228699,{3692314992156390409935188832247879690835442533596382120243742164226816404074858551895396887014271276961042875407,3,2}},{8}],Table[{2057694758803,{,3,3}},{20}]];
 ic ={{0,0,0,1,1,1,0,0,0,1,2,1,0,0,0,1,2,1,0,0},0};

DemoRR[sr[[8]],NSteps->30,IC->ic]

Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas 
		(a.) one dimension	- 3 colors

The invert rules of some k=3,r=1 reversible rules require a range r>1:

DemoRR[sr[[10]],NSteps->30, IC->ic,   InvertRange->2]

DemoRR[sr[[28]],NSteps->25,InvertRange->3,IC-> ic]

Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas
		(b.) application to inverse problems in engineering?

It is evident that reversible CA rules, in some sense, "preserve" system information from one step to the next.   Thus, reversible CA rules might be a natural representations for modelling of physical systems (conservation principles).
                     
Of interest in this research are inverse problems,  which generally have non-unique solutions.
     o Measurement/instrumentation applications are practical examples of inverse problems.
     o Inverse problems difficult to solve by conventional computation; are necessarily iterative. 


Reversible CA strategies for inverse problems might prove advantageous as compared to conventional floating-point (finite element, finite difference, etc.) :
        (1)  With inverse problems the objective often is a qualitative judgement;                        
        (2)  Inverse-problem solvers are necessarily iterative: 
               o conventional approach:  "system state" is re-estimated and computed forward
               o reversible CA strategy:   a bi-directional search may be possible

Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas
		(c.) model problem in optical metrology

The in-process inspection of wafers during integrated-circuit manufacture: what they have...

Reversible CA/Inverse problems in engineering
		(I.) Basic Ideas
		(c.) model problem in optical metrology

The in-process inspection of integrated-circuit  manufacture: what they would like...

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(a.) two options for reversible CA construction

Optical metrology is a two-dimensional problem, so we require two-dimensional reversible cellular automata constructions.

However, it the invertibility of any basic two-dimensional rule  (where a cell's state is determined from a rule defined over a local 2-d neighborhood)  is formally undecidable.

Are we stuck?           

Not yet. Now we will look at two other approaches for generating reversible CA algorithms in two dimensions:

                         (1)   Second-order Fredkin scheme
                         (2)  Block-transformation-rule "Margolus Neighborhood" scheme.

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(b.) the second-order Fredkin construction
		            (i.) definition of the algorithm

The Fredkin construction, attributed to Edward Fredkin, creates k-color reversible rules as follows:

                                                           (SuperPlus[A])= mod[ ruleX(A) - (SuperMinus[A]), k] .

Here,           (SuperPlus[A])                 is the state of the cells, to be computed next;
                   A                    is the state of the cells in the current step;
                   (SuperMinus[A])                 is the state of the cells in the prior step;
                   ruleX()           a (non totalistic) CA rule, in k colors, operating on A.         
                    
To invert this rule one need only reverse two successive states of A, and run it backwards....

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(b.) the second-order Fredkin construction
		            (iii.) Fredkin CA evolutions in 1-d

(* time 0 *)   ic1d3k = Table[If[jj==0,1, If[Abs[jj]==2,2,0]],{jj,-20,20}];  
(* time 1 *)   ic1d00 = Table[0,   {jj, -20,20}];                                                                                                  
FredkinBuiltin[{50,3}, ic1d00,ic1d3k, 3, 20];

Although color is not conserved from step to step, the evolution is clearly reversible.   Since 2 successive states are requisite to define a reversible Fredkin sequence, this suggests that the Fredkin construction might be a natural representation for (mathematically second-order)  mechanics and/or dynamics problems .

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(b.) the second-order Fredkin construction
		            (iv.) Fredkin CA evolutions in 2-d

ic2d3k = Table[If[ii==jj,1,If[Abs[ii-jj]==2,2,0]],{ii,20},{jj,20}];   (* time 0 *)
ic2d00 = Table[0,{20},{20}];                                                                                                           (* time 1 *) 
FredkinBuiltin[{1552,3,{1,1}},ic2d00, ic2d3k,3, 14]

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(c.) the Block-transform "Margolus-neighborhood" scheme
		            (i.) 4-cell "block" transformation rules

Basic idea:
            o the 2-d CA field is subdivided into contiguous 2x2 blocks  of cells
            o the rules transform each 2x2 block (to another block configuration) in situ
            o not necessarily reversible
            
To make it reversible:
            o the transformation rule must conserve color
            o in the rule each block configuration must occur exactly once as a source and target.
            o to reverse a rule so constructed, we merely reverse the sense of the arrows

Here is an example of a 2-color rule.

MaxBlockCARule[2,4]

rl2 = BlockCARuleSet[12341,2,4];

VisualizeBlockRule[rl2,2,8];

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(c.) the Block-transform "Margolus-neighborhood" scheme
		            (ii.) 4-cell "block" transformation rules - 3 colors

One can enumerate all block reversible rules of this type.
	n 	= MaxBlockCARule[ k, b]	           gives the max rule number; rules numbered 0,1,2,...n 
	subslist  = BlockCARuleSet[rn, k, b]	returns substitution-rule list for rule rn in my enumeration
	
Here is a 3-color rule.

MaxBlockCARule[3,4]

rl3 = BlockCARuleSet[123432123,3,4];

VisualizeBlockRule[rl3,2,8];

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(c.) the Block-transform "Margolus-neighborhood" scheme
		            (iii.) the 2-step shifted-block-definition concept

So that information propagates in the 2-D CA field the rule is applied in two passes 
                  (1) pass one:  cells 1-4 transform within the same block (see b)
                  (2) pass two:  block definitions are shifted over and up by one;
                                       now cells 1-4 each transform within a different block (see c).

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(c.) the Block-transform "Margolus-neighborhood" scheme
		            (iv.) sample evolutions

BlockEvolveDisplay[373737,2,{2,2},Table[If[i*j==0,1,0],{i,-6,5},{j,-5,6}],6];

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(c.) the Block-transform "Margolus-neighborhood" scheme
		            (v.) extension to "identity colors"

Looking ahead, irregular and "to be determined" boundaries will be considered.    
                    ->This necessitates the concept of what I call identity colors:
                        a cell of a certain color always remains that color.

For example, lets declare red (#2) as an "identity color" and see what the rule looks like.

MaxBlockCARule[3,4, {2}] (* far fewer rules! *)

rl3ident = BlockCARuleSet[123432123,3,4,{2}];

VisualizeBlockRule[rl3ident,2,8,IdentityColors->{2}];

VisualizeBlockRule[rl3ident,2,8,IdentityColors->{2}, OnlyMutableConfigurations -> True];

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(c.) the Block-transform "Margolus-neighborhood" scheme
		            (v.) extension to "identity colors" - an evolution

BlockEvolveDisplay[373737,{3,{2}},{2,2},Table[If[i*j==0,If[i==0,1,2],0],{i,-6,5},{j,-5,6}],6];

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(d.) Fredkin/Block-transform in conjunction
		            (i.) basic code

The capability of utilizing irregular  boundaries (identity colors)   within the second-order Fredkin approach is attractive.

Why not make a block-Margolus evolution scheme the "ruleX" of the Fredkin method?  This works if you limit the identity colors to the topmost colors and apply the mod()  feature only to the lower-order colors.

ic = Table[If[ii==jj,1,If[ii-jj==2,2,0]],{ii,16},{jj,16}];
FredkinMargolus[ 1234567, ic,ic,{3,{2}}, 10]

Reversible CA/Inverse problems in engineering
		(II.) Two-dimensional reversible CAs
		(e.) Extension to hexangonal domain definitions

Finally, in the Margolus-neighborhood scheme, we can use other kinds of interlocking block arrangements: for example     hexangular blocks of six triangles.

Reversible CA/Inverse problems in engineering
		(III.) Future Work -- next task

Would like, next, to work out inverse solution methodology (using CAs) on a simpler problem than light scattering...