Displaying similar documents to “Language classes defined by time-bounded relativised cellular automata”

Some results on cellular automata

Claudio Baiocchi (1998)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

Similarity:

We want to discuss some properties of one-dimensional, radius 1, CUCAs (we denote by CUCA a Computationally Universal Cellular Automaton; see later on for the definitions). In particular, on one hand we want to keep small the number of states (the first example of «small» CUCA is due to Smith III [13]; it requires 18 states); on the other hand we are interested into automata, possibly requiring a high number of states, whose transition law is «as simple as possible»; e.g. totalistic...