کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430007 687773 2015 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A uniquely ergodic cellular automaton
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A uniquely ergodic cellular automaton
چکیده انگلیسی

We construct a one-dimensional uniquely ergodic cellular automaton which is not nilpotent. This automaton can perform asymptotically infinitely sparse computation, which nevertheless never disappears completely. The construction builds on the self-simulating automaton of Gács. We also prove related results of dynamical and computational nature, including the undecidability of unique ergodicity, and the undecidability of nilpotency in uniquely ergodic cellular automata.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 81, Issue 2, March 2015, Pages 415–442
نویسندگان
,