Modelling and Simulating Cellular Automata

Cellular automata (CA) consists of a simple and well-formalized model of massively parallel computing, known to be capable of universal computing. CA has rich information processing capabilities because of their parallel behaviour; however, defining their power limitations is not easy. It is a useful approach to classifying the computational capacity of CA to examine their complexity classes.

There are many fundamental open problems with cellular automata. For example:

1 Is the RPCA language class closed (concatenation) under reversal?

2 Is LPCA stronger than RPCA?

3 Is PCA more powerful than LPCA?

In this paper I explained the questions and explained what has been done so far.