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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2018

All Science Journal Classification (ASJC) codes

  • !!General Computer Science
  • !!Control and Systems Engineering

بصمة

أدرس بدقة موضوعات البحث “Complexity steering in cellular automata'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا