Cellular Systems Flashcards
1
Q
Name the four building blocks of Cellular systems
A
- Cell and cellular space
- Neighbourhood (local interaction)
- Cell state
- Transition rule
2
Q
Name two types of neighbourhood in grid CA systems
A
von Neumann
Moore (Moore has more cells in neighbourhood)
3
Q
The 4 types of BC in CA
A
Assigned, Periodic, Adiabatic and Reflection
4
Q
How to run a CA
Steps in practice are:
A
- Assign geometry of the CA space
- Assign the geometry of the neighbourhood
- Define the set of states of the cells
- Assign the transition rule
- Assign the boundary conditions
- Assign the initial conditions of the CA
- Repeatedly update all the cells of the CA, until some stopping condition is met
5
Q
Informal definition of CA
A CA is:
A
- a geometrically structured and
- discrete collection of
- identical (simple) systems called cells that
- interact only locally
- with each cell only having local state memory that can take a finite number of values
- and a (simple) rule used to update the state of all cells
- at discrete time steps
- and synchronously for all cells of the automaton
6
Q
Formula for total number of possible CA and totalistic CA given that range of cells included in neighbourhood r=1 and number of states K
A
K^K^3
and
K^(3K-2)
7
Q
What are the four qualitative behavioural classes?
A
Uniform final state
Simple stable or periodic final state
Chaotic, random, non-periodic patterns
Complex, localised, propagating structure
8
Q
Can CAs be used to compute anything?
A
Yes, they are capable of universal computation
