Sunday, December 19, 2010

XOR using string rewriting

Can XOR to be constructed using string rewriting and iterating such rules like the following:

0 -> 0 0
0 2

1 -> 2 2
2 4 ?