What is a cellular automaton?

5

What is the cellular automaton? What kind of problem can you solve? Is this equivalent to Turing machines ?

    
asked by anonymous 28.07.2017 / 16:06

1 answer

1
  

What is the cellular automaton?

The first definition of Automato Celular came up with Von Neumman in the 1940s  with the intention of providing information on the logical requirements of a Machine  self-replicator, and was used in the von Universal Builder  Neumann .

In a general definition, Cellular Automata , mathematically speaking, is an arrangement of states machines that there are changes between them based on pre-established conditions.

  

The CA is composed of a set of cells with certain values, which interact   among them in function of a finite collection of pre-defined conditions. The states (values) of the cells are changed according to a set of transition rules, which   depends on the neighborhood (sometimes the cell itself), that is, the cells in   around the cell that will be updated.

Worth stressing about the Finite collection of predefined conditions .

  

Evolutionofacellularautomatoninadimensionnetwork  1andinanetworkofdimension2withhexagonalsymmetry.Theruleof  interactionisthesameforthetwoautomata:thestateofeachnode  intime1onlydependsonthestatesintheneighboringnodesattime0

Let'stakeasreferencetheone-dimensionalautomata,Wehaveexactly256rulesdefined:

  

Eachcellcanassumeoneofthepossiblestates(values)kof  setQ,wherestatesvaryfrom0tok-1.

Becauseitisone-dimensional,itwillhaveonlytwopaths(commonlycalledneighbors),onetotherightandonetotheleft(disregardingthek-pointitself)

  

A  possiblecombinationsofthetwoneighborsandthecellitselfandtwo  statesis2³=8combinations,wherethecellswillhaveonlyoneofthetwostates  thatis,thenumber2correspondstothenumberofpossiblestatesthatthe  cellcanassume,forexample0or1,andthenumber3correspondstotheamountof  neighbors,thatis,theneighborontheleft,thecellitselfandtheneighborontheright,which  impliesaneighborhoodrangeequaltor=1.Withthese8possiblecombinations  atotalof2⁸=256localrulescanbeformed,ieforeachcombinationthecellthatwillbeupdatedcanreceive0or1.

Inshort,theACsrepresentcertainsetsthatwillbemodifiedbyestablishedrulesandthisimpliestheanswertothesecondquestion:

  

**Whatkindofproblemcanyousolve?**

BydemonstratingtheresultsfromrulestheACsareusedtosimulatephenomena,itispossibletosimulatethepropagationofafireifweareinastrongdroughtandthewindis10knotstothewest,forexamplelogicallytheeasternpartofthebeginningwouldbemuchless,ortherewouldbenofocusoffireandthepartburningwhenitfinishedthetreesand/orfoundsomeregionofmuchrockwouldendthefire.

  

IsitequivalenttoTuringmachines?

Similar,butnotequivalent.WhiletheAcswouldworkwithpre-definedvaluesofFinitesets,resemblingTapeMachine,butforTuringtherewasunlimitedpotentialfortapes.

  

isamachinecapable  tocalculatealltheprocessesorfunctionsthatweare  abletoimagine

ThisquestionclearlydefinesthemeaningoftheTuringMachine What is a Turing Machine ?

Other references: Cellular Automata, Turing Machine or Nature As a Calculation Machine

    
24.08.2017 / 23:27