What is the cellular automaton? What kind of problem can you solve? Is this equivalent to Turing machines ?
What is the cellular automaton? What kind of problem can you solve? Is this equivalent to Turing machines ?
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