What is a cellular automaton?

Question

What is the cellular automaton about? What kind of problem can it solve? It’s something equivalent to turing machines?

Answer 1

What the cellular automaton is about?

The first definition of Automato Celular Came up with Von Neumman in the '40s intended to provide information on the logical requirements of a Machine self-replicating, and was used in universal builder of Von Neumann.

In a general definition, Cellular Automaton, mathematically speaking , is an arrangement of state machines that there are changes among themselves based on pre-established conditions.

AC is composed of a set of cells with certain values, which interact as a function of a finite collection of predefined conditions. The states(values) of the cells are modified according to a set of transition rules, which depends on the neighborhood (sometimes of the cell itself too), ie of the cells in cell lathe that will be updated.

Vale Ressalva on the stretch finite collection of predefined conditions.

Evolution of a cellular automaton in a network of dimensions 1 and in a network of dimension 2 with hexagonal symmetry. The rule of interaction is the same for both automatos: the state of each node in time 1 only depends on the states in the neighboring nodes in time 0

Let’s take one-dimensional automata as a reference, we have exactly 256 rules defined:

Each cell can assume one of the possible states (values) k of the set Q, with states ranging from 0 to k 1.

Because it is one-dimensional, it will have only two paths (commonly called neighbors), one to the right and one to the left (disregarding point k itself)

To possible amount of combinations with the two neighbors and the cell itself and two states is 2³ = 8 combinations, and the cells will have only one of the two states the number 2 corresponds to the number of possible states cell can assume, for example 0 or 1, and the number 3 corresponds to the amount of neighbors, that is, the neighbor on the left, the cell itself and the neighbor on the right, which implies a neighborhood band equal to r = 1. With these 8 possible combinations can form a total of 2 = 256 local rules, that is, for each combination the cell that will be updated can receive 0 or 1.

In short, Chws represent certain sets that will be amended by established rules and this implies in the answer to the second question:

** What kind of problem can you solve?**

By demonstrating the results from rules Acs are used to simulate phenomena, it is possible to simulate the spread of a fire if we are in a severe drought and the wind is 10 knots west, for example logically the eastern part of the beginning would be much less, or there would be no focus of fire and the burning part when it finished with the trees and/or found some region of much rock would end the fire.

It’s something equivalent to Turing machines?

Similar but not equivalent. While Acs would work with predefined set values Finite, resembling the tape machine, but for Turing there was an unlimited potential of tapes.

is a machine capable to calculate all processes or functions that we are able to imagine

This question defines well the meaning of the Turing machine What is a Turing machine?

Other references : Cellular automata, Turing machine or nature as a calculation machine