Computing by nowhere increasing complexity

Bar Y. Peled, Vikas K. Mishra, Avishy Y. Carmi

A cellular automaton is presented whose governing rule is that the Kolmogorov complexity of a cell's neighborhood may not increase when the cell's present value is substituted for…