Complexity steering in cellular automata

Bar Y. Peled, Avishy Y. Carmi

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

A cellular automaton is presented whose governing rule is that the Kolmogorov complexity of a cell’s neighborhood may not increase when the cell’s present value is substituted for its future value. Using an approximation of this two-dimensional Kolmogorov complexity, the underlying automaton is shown to be capable of simulating binary logic circuits. A similar automaton whose rule permits at times the increase of a cell’s neighborhood complexity is shown to produce animated entities that can be used as information carriers akin to gliders in Conway’s Game of Life. The element that repeatedly generates gliders, the glider gun, is constructed in this automaton using a number of self-replicating mechanisms. Moreover, gliders’ annihilation and creation allow constructing logic gates as well as data encoding mechanisms.

שפה מקוריתאנגלית
עמודים (מ-עד)159-175
מספר עמודים17
כתב עתComplex Systems
כרך27
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2018

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1700???
  • ???subjectarea.asjc.2200.2207???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Complexity steering in cellular automata'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי