اتوماتای سلولی

الگوهای منظم گاسپرن گلایدرهای منظمی را برای بازی زندگی کانوی می‌سازند

اتوماتای سلولی مدلی از ریاضیات گسسته است که در مباحثی چون نظریه محاسبه‌پذیری، ریاضیات، فیزیک، سامانه‌های انطباقی پیچیده، زیست‌شناسی نظری و ریز ساختارها مورد مطالعه قرار گرفته‌است. اتوماتای سلولی با نام‌هایی مانند فضاهای سلولی، اتوماتای مفروش سازی، ساختارهای همگن، ساختارهای سلولی، ساختارهای مفروش سازی و آرایه‌های تکرار شونده نیز بیان می‌گردد.

یک اتوماتای سلولی شامل یک شبکه منظم از سلول‌ها است که هر کدام از آن‌ها در یکی از حالات از مجموعه حالات متناهی امکان‌پذیر قرار دارند. مانند on و offیا مقدار منطقی 0 و 1.همچنین شبکه می‌تواند هر بعد متناهی داشته باشد. برای هر سلول، یک مجموعه از سلول‌ها که همسایهٔ آن نامیده می‌شود، نسبت به آن سلول مشخص تعریف شده‌است. یک حالت آغازین (time = ۰)یا(t=0) با تخصیص دادن یک وضعیت به هر سلول انتخاب می‌شود. یک نسل جدید (توسعه t به وسیله ۱)، بر اساس یکسری قوانین ثابت (عموماً یک تابع ریاضی) که وضعیت جدید برای هر سلول را بر اساس وضعیت جاری آن سلول و وضعیت‌های سلول‌های همسایه آن، مشخص می‌کند، تولید می‌شود. به‌طور معمول، قوانین به روزرسانی وضعیت سلول‌ها برای هر سلول مشابه است و در طول زمان تغییر نمی‌کند، و به کل شبکه به صورت هم‌زمان اعمال خواهد شد، هر چند استثناهایی نیز وجود دارد، مانند اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام.

این مفهوم در ابتدا در دهه ۴۰ میلادی، به وسیله استنی‌سواف اولام و جان فون نویمان در حالی که آن‌ها در آزمایشگاه ملی لس آلاموس بودند، کشف شد. این موضوع در دهه ۵۰ و ۶۰ میلادی نیز توسط برخی مورد مطالعه قرار گرفت ولی تا دهه ۷۰ و مطرح شدن بازی زندگی کانوی، یک اتوماتای سلولی دو بعدی، که علاقه به این موضوع را به ابعادی فراتر از بحث‌های دانشگاهی گسترش داد، هنوز وجود نداشت. در دهه ۸۰، استیون ولفرم، که درگیر مطالعه سیستماتیک یک اتوماتای تک بعدی یا چیزی که او اتوماتای سلولی بنیادی می‌نامید، بود، دستیار تحقیقاتی او متیو کوک نشان داد که یکی از این قوانین، کامل بودن تورینگ است. ولفرم مقاله‌ای با عنوان جنبه دیگری از علوم (به انگلیسی: A New Kind of Science) را در سال ۲۰۰۲ منتشر نمود. او در این مقاله مدعی شد اتوماتای سلولی در بسیاری از حوزه‌های علوم کاربرد دارد. از جمله آن‌ها می‌توان به کاربرد آن در پردازنده‌های کامپیوتری و رمزنگاری اشاره کرد.

طبقه‌بندی اولیهٔ اتوماتای سلولی که توسط ولفرم اشاره گردید از ۱ تا ۴ شماره‌گزاری شده‌است. این طبقه‌بندی‌ها به ترتیب بدین صورت هستند: اتوماتایی که در آن الگوها به‌طور کلی به صورت همگن تثبیت شده‌اند، اتوماتایی که الگوها در آن به ساختارهای اغلب نوسانی یا با ثبات توسعه یافته‌اند، اتوماتایی که در آن الگوها در آن به یک قالب ظاهراً بی نظم توسعه یافته‌اند و اتوتایی که در آن الگوها کاملاً پیچیده شده‌اند و ممکن است برای مدت زمان طولانی به همراه ساختارهای محلی با ثبات، باقی بمانند. این طبقه آخر به نظر می‌رسد از منظر کامل بودن تورینگ صحیح بوده یا قادر به شبیه‌سازی یک ماشین تورینگ باشد. انواع خاص از اتوماتای سلولی این‌ها هستند که برگشت‌پذیر هستند که در آن فقط یک پیکربندی مستقیماً به … بعدی منجر می‌شود، و توتالیستیک هستند که در آن مقدار آیندهٔ سلول‌های منفرد به ارزش کل یک گروه از سلول‌های همسایه بستگی دارد. اتوماتای سلولی می‌تواند انواع گوناگونی از سیستم‌های دنیای واقعی شامل سیستم‌های زیستی و شیمیایی را شبیه‌سازی کند.

چکیده

یک چنبره، یک شکل چنبره ای

یک راه برای شبیه‌سازی اتوماتای سلولی دو بعدی، استفاده از تعداد متناهی صفحات کاغذ میلی‌متری به همراه مجموعه از قوانین برای سلول‌ها می‌باشد. هر مربع یک «سلول» نامیده می‌شود و برای هر سلول دو حالت امکان‌پذیر است، سیاه و سفید. همسایه‌های سلول نزدیکترین و معمولاً سلول‌های مجاور آن هستند. دو نوع از رایج‌ترین انواع همسایه‌ها، همسایه‌های فون نویمان و همسایه‌های مور هستند. مدل اول، پس از مطرح شدن نظریه‌پرداز اتوماتای سلولی، شامل چهار سلول تعامد (جبر خطی)، نامگذاری شد. مدل دوم شامل همسایه نوع فون نویمان هست و علاوه بر آن چهار سلول باقی‌مانده در اطراف سلولی که باید حالتش محاسبه شود را نیز شامل می‌گردد. برای یک چنین سلولی و همسایه نوع مور آن، ۵۱۲ الگوی امکان‌پذیر وجود دارد. برای هر یک از ۵۱۲ الگوی امکان‌پذیر، جدول قوانین مشخص خواهد کرد که حالت سلول مرکزی در فاصله زمانی بعدی سیاه یا سفید خواهد بود. بازی زندگی کانوی یک نسخه محبوب و عمومی از این مدل است. یک مدل رایج دیگر از انواع همسایه، همسایه مدل فون نویمان بسط یافته‌است که شامل دو نزدیک‌ترین سلول در هر جهت متعامد، برای کل هشت خانه، می‌باشد. معادله عمومی برای چنین سیستمی از قوانین، k به قوه k به قوه s می‌باشد که K در آن تعداد حالت‌های ممکن برای یک سلول و S تعداد سلول‌های همسایه (از جمله خود سلولی مورد نظر) که به منظور تعیین حالت بعدی سلول مورد استفاده قرار می‌گیرد؛ بنابراین در یک سیستم دوبعدی با همسایه از نوع مور، تعداد کل اتوماتای ممکن برابر است با2²⁹, یا۷۱۵۴۱۳۴۰۰۰۰۰۰۰۰۰۰۰۰♠۱٫۳۴×۱۰^۱۵۴. اغلب فرض می‌شود همه سلول‌ها در جهان از یک حالت یکسان شروع می‌شوند، به جز برای تعداد متناهی سلول در حالت‌های دیگر؛ فرایند تخصیص مقادیر به حالت‌ها پیکربندی نامیده می‌شود. به‌طور کلی، گاهی اوقات فرض می‌شود جهان در آغاز با یک الگوی تناوبی پوشش داده شده‌است و فقط تعداد متناهی از سلول‌ها از این الگو پیروی نمی‌کند. فرض دوم در اتوماتای سلولی یک بعدی رایج است.

اتوماتای سلولی اغلب بر روی شبکه متناهی شبیه‌سازی می‌شود تا یک شبکه نامتناهی. در حالت دو بعدی، جهان باید به صورت چهارگوش باشد به جای یک صفحه نامتناهی. مشکل مشاهده شده در مورد شبکه‌های محدود این است که چگونه سلول‌ها را در گوشه‌ها مدیریت نماییم. نحوه مدیریت آن‌ها بر روی مقادیر همهٔ سلول‌ها در شبکه تأثیرگزار خواهد بود. یکی متد امکان‌پذیر این است که اجازه دهیم مقادیر در این سلول‌ها ثابت باقی بمانند. یک متد دیگر می‌تواند این باشد که همسایه را برای این‌گونه سلول‌ها به گونه‌ای متفاوت تعریف نماییم. ممکن است یک نفر بیان کند که این سلول‌ها همسایه‌های کمتری دارند، اما در این صورت مجبور به تعریف قوانین جدیدی برای سلول‌های موجود در گوشه‌ها خواهیم بود. این سلول‌ها معمولاً با یک ترتیب toroidal مدیریت می‌شوند. این می‌تواند بدین صورت تصویرسازی شود که گوشه‌ها چپ و راست چهارگوش را به یکدیگر متصل نموده و یک تیوپ ایجاد نماییم، سپس بالا و پایین گوشه‌های تیوپ را به یکدیگر متصل نموده و یک چنبره (شکلی همانند حلقه) ایجاد نماییم. فضاهای مربوط به سایر ابعاد به شیوه‌ای مشابه مدیرت می‌شوند. این کار به منظور حل مشکل حدود مرزی در همسایگی‌ها انجام شده‌است، اما یک مزیت دیگر این سیستم این است که به راحتی توسط توابع هم‌نهشتی (نظریه اعداد) قابل برنامه‌ریزی است. به عنوان مثال، در یک اتوماتای سلولی تک بعدی، مانند مثال زیر، همسایگی سلول xit برابر است با {xi−1t−1, xit−1, xi+1t−۱}، که t گام‌های زمانی (قایم)، و i ایندکس (افقی) در یک گسترش می‌باشد.

تاریخچه

جان فون نویمان، نشان شناسایی در آزمایشگاه ملی لس آلاموس

استنی‌سواف اولام، زمانی که در آزمایشگاه ملی لس آلاموس، در دهه ۴۰ میلادی مشغول به کار بود، بر روی رشد کریستال‌ها با به‌کارگیری یک مدل شبکه توری منظم به عنوان مدل خود، مطالعه می‌نمود. در همان زمان، جان فون نویمان، همکار اولام در لس آلاموس، بر روی مشکلات سیستم‌های خود تکرار یا همان خودجایگزین‌گری کار می‌کرد. طراحی اولیه ون نیومن بر اساس ساخته شدن یک ربات توسط یک ربات دیگر بنا نهاده شد. این طراحی به عنوان مدل حرکتی شناخته می‌شود. در روند توسعه این طراحی، ون نیمن متوجه مشکل بزرگی در زمینه ساخت یک روبات خود تکرار شد، و هزینه بالای در تولید ربات به همراه دریایی از قطعات که برای ساخت تکرارش نیاز دارد نیز از دیگر مشکلات است. نیومن یک مقاله با عنوان «نظریه منطقی و عمومی اتوماتا» در سال ۱۹۴۸ در نشست هیگزون مطالعه کرد. اولام کسی بود که پیشنهاد استفاده از یک سیستم گسسته برای ایجاد یک مدل کاهش یافته از مدل خود تکرار را مطرح نمود. نیلز آل باریچرلی بسیاری از کشفیات اولیه در زمینه این مدل‌های زندگی مصنوعی را انجام داده‌است.

اولام و ون نیومن یک متد به منظور محاسبه حرکت مایع در اواخر دهه ۵۰ میلادی ایجاد نمودند. مفهوم مؤثر این متد در نظر گرفتن مایع به عنوان گروهی از واحدهای گسسته و محاسبه حرکت هر کدام بر اساس رفتار همسایگان خود بوده‌است. بدین سان اولین سیستم اتوماتای سلولی متولد شد. همانند شبکه توری منظم اولام، اتوماتای سلولی طراحی شده توسط ون نیومن به صورت دو بعدی با الگوریتم خود تکرار او پیاده‌سازی شده‌است. نتیجه یک سازنده کپی‌کننده جهانی که با یک اتوماتای سلولی و مجموعه کوچکی از همسایگان. (فقط این سلول‌هایی که با آن‌ها در تماس هستند به عنوان همسایه محسوب می‌شوند، برای اتوماتای سلولی مدل ون نیون، فقط سلول‌های متعامد) و ۲۹ حالت برای هر سلول، بود. ون نیومن یک نظریه اثبات وجود مطرح نمود که یک الگوی مشخص، یک کپی بی پایان از خود را درون جهان سلولی داده شده به وسیله طراحی پیکره بندی ۲۰۰۰۰۰ سلول که بتوانند چنین کاری انجام دهند، ایجاد خواهد نمود. این طراحی با عنوان مدل موزائیک‌کاری (به انگلیسی: Tessellation) شناخته شده‌است و با نام سازنده جهانی ون نیومن نامیده می‌شود.

همچنین در دهه ۴۰ میلادی، نوربرت وینر و آرتور رونزبلاس یک مدل از رسانه‌های تحریک پذیر را با به‌کارگیری برخی ویژگی‌های یک اتوماتای سلولی توسعه دادند. انگیزه اصلی آن‌ها، توصیف ریاضی انتقال ضربه در سیستم‌های قلبی بود. با این وجود مدل آن‌ها یک اتوماتای سلولی نیست زیرا حداقل، انتشار سیگنال در آن پیوسته و جبهه‌های موج به صورت منحنی است. یک مدل اتاماتای سلولی صحیح از رسانه تحریک پذیر توسط گرینبرگ و هستینگ در سال ۱۹۷۸ توسعه یافته و مورد مطالعه قرار گرفت. کار اصلی وینر و رونزبلاس شامل نگرش‌های مختلفی است و همچنان در نشریان مدرن تحقیقاتی در زمینه بی نظمی قلبی و سیستم‌های تحریک پذیر مطرح می‌باشد.

در دهه ۶۰ میلادی اتوماتای سلولی به عنوان بخش مشخصی از سیستم پویا مورد مطالعه قرار گرفت و اتصال آن با مبحث ریاضیاتی از پویایی سمبلیک برای اولین بار محقق گردید. در سال ۱۹۶۹، هدلند نتایج زیادی را مبتنی بر همین دیدگاه گردآوری نمود. چیزی که هنوز هم به عنوان یک مقاله اصلی برای مطالعه ریاضیاتی اتوماتای سلولی در نظر گرفته می‌شود. اساسی‌ترین نتیجه، در توصیف ویژگی‌های نظریه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) در مورد اینکه مجموعه قوانین سراسری اتوماتای سلولی به عنوان مجموعه‌ای از درون دگرگونی‌های پیوسته از فضای تغییر است.

در سال ۱۹۶۹، پیشگام کامپیوتر آلمانی، کنراد تسوزه، کتاب خود را با عنوان فضای محاسبه (به انگلیسی: Calculating Space) منتشر نمود. او در این کتاب مطرح نموده‌است که قوانین فیزیکی جهان توسط طبیعت گسسته شده‌است، و کل جهان خروجی یک محاسبه قطعی در یک ماشین سلولی منفرد است. نظریه تسوزه، بنیانی برای شاخه‌ای علوم با نام فیزیک دیجیتال قرار گرفت.

در دهه ۷۰ میلادی، یک اتوماتای سلولی دو حالتهٔ دوبعدی با نام بازی زندگی (به انگلیسی: Game of Life) به صورت گسترده‌ای شناخته شد، بخصوص در انجمن‌های محاسباتی اولیه. این اوتوماتا توسط جان کانوی اختراع و توسط مارتین گاردنر در مقاله علمی آمریکایی به شهرت رسید. قوانین آن به صورت زیر است: اگر یک سلول دارای دو بلاک همسایه باشد، به همان صورت قبل باقی می‌ماند. اگر سه بلاک همسایه داشته باشد، سیاه می‌شود. در همهٔ شرایط دیگر، آن سلول سفید خواهدشد. بر خلاف سادگی آن، سیستم به تنوع قابل توجهی در رفتار دست پیدا خواهد نمود، که در حال نوسان به صورت رندوم ظاهری یا منظم هست. یکی از آشکاراترین ویژگی‌های بازی زندگی رخ دادن تکرار شوندهٔ گلایدرها (ترتیبی از سلول‌ها که بنا به ضرورت خودشان را در شبکه جابجا می‌کنند) است. این امکان‌پذیر است که به گونه‌ای اتوماتا را سازماندهی نماییم که گلایدرها به منظور انجام محاسبات با یکدیگر تعامل داشته باشند، و پس از تلاش‌های زیاد، این نشان داده شد که بازی زندگی می‌تواند با یک تورینگ ماشین جهانی برابری نماید. این مسئله به عنوان یک موضوع تفریحی تصور شده و کارهای بسیار کمی خارج از چارچوب بررسی خصوصیات بازی زندگی و اندک قوانین مرتبط با آن در دهه ۷۰ میلادی انجام پذیرفت.

استیون ولفرم به صورت مستقل کار بر روی اتوماتای سلولی را در اوسط سال ۱۹۸۱، پس از بررسی الگوهای پیچیده در طبیعت و نحوه شکل‌گیری آن‌ها بر خلاف قانون دوم ترمودینامیک، آغاز نمود. تحقیقات او در ابتدا با تمرکز بر روی سیستم‌های مدلسازی مانند سیستم‌های عصبی آغاز شده بود. او اولین مقاله اش را در ژورنال Reviews of Modern Physics که تحقیق و بررسی بر روی اتوماتای سلولی پایه (به‌طور خاص اتوماتای ۳۰ قانونه) بود، در سال ۱۹۸۳ منتشر نمود. پیچیدگی غیرقابل انتظار در رفتار چنین قانون‌هایی، ولفرم را به این جهت سوق داد که به این موضوع شک کند که پیچیدگی موجود در طبیعت نیز ناشی از مکانیزم مشابه‌ای باشد. با این وجود، تحقیقات او موجب شد، او دریابد که اتوماتای سلولی سیستم مدلسازی ضعیفی به منظور مدلسازی سیستم‌های عصبی محسوب می‌شود. علاوه بر این، در طی این همین زمان، ولفرم مفاهیم ذاتاً تصادفی بودن و تقلیل ناپذیری را فرموله بندی نموده و پیشنهاد داد که اتوماتای ۱۱۰ قانونه ممکن است همگانی باشد - این حقیقت بعداً توسط متیو کوک، دستیار تحقیقاتی ولفرم، در سال ۱۹۹۰ اثبات گردید.

در سال ۲۰۰۲، ولفرم یک مستند ۱۲۸۰ صفحه‌ای با نام جنبه جدید از علوم (به انگلیسی: A New Kind of Science) منتشر نمود. در این متن، ولفرم در مورد اینکه اکتشافات انجام شده در زمینه اتوماتای سلولی حقایق مجزا و منحصر به فردی نیستند ولی قدرتمند بوده و برای همهٔ رشته‌های علمی پراهمیت هستند، استدلال‌های گسترده‌ای را مطرح نمود. علی‌رغم سردرگمی زیاد مطبوعات، این کتاب در مورد نظریه اساسی فیزیک مبتنی بر اتوماتای سلولی استدلالی مطرح نمی‌نماید. هر چند این کتاب تعداد کمی از مدل‌های خاص فیزیکی مبتنی بر اتوماتای سلولی را توصیف می‌نماید و همچنین مدل‌هایی مبتنی بر سیستم‌های انتزاعی با کیفیت‌های متفاوت، ارائه می‌نماید.

طبقه‌بندی

ولفرم، در کتاب جنبه جدید از علوم و مقالات بسیاری در سال‌های مربوط به اواسط دهه ۸۰ میلادی، چهار کلاس را در زمینه چگونگی تقسیم‌بندی اتوماتای سلولی و بسیاری از مدل‌های ساده محاسباتی دیگر بر اساس رفتارشان، توصیف نمود. در حالی که مطالعات قبلی در زمینه اتوماتای سلولی، به منظور تعیین نمودن انواع الگوها برای هر قانون مشخص بود، طبقه‌بندی مطرح شده توسط ولفرم، اولین تلاش در زمینه طبقه‌بندی خود قوانین بود. به ترتیب پیچیدگی، این کلاس‌های بدین شرح می‌باشند:

• کلاس اول: تقریباً تمام الگوهای پایه که به سرعت به یک حالت همگن و با ثبات توسعه می‌یابند. هیچ گونه تصادفی بودنی در الگوی پایه در نظر گرفته نخواهد شد.
• کلاس دوم: تقریباً تمام الگوهای پایه که به سرعت به یک ساختار با ثبات یا نوسانی توسعه می‌یابند. برخی از موارد تصادفی، در این الگوی پایه در نظر گرفته نمی‌شود اما برخی از آن‌ها نیز لحاظ می‌گردد. تغییرات محلی بر روی الگوی پایه، تمایل دارند به صورت محلی باقی بمانند.
• کلاس سوم: تقریباً تمام الگوهای اولیه که به صورت شبه تصادفی و بی نظم توسعه می‌یابند. هرگونه ساختار با ثباتی که ظاهر شوند به سرعت توسط نویزهای اطراف از بین خواهند رفت. تغییرات محلی در الگوی پایه تمایل دارند به صورت نامحدودی منتشر شوند.
• کلاس چهارم: تقریباً تمام الگوهای اولیه که به ساختارهایی با روش‌های پیچیده و جالب تعامل و با شکل‌گیری ساختارهای محلی که قادر به زنده ماندن برای مدت طولانی هستند، توسعه پیدا می‌کنند. کلاس نوع دوم، ساختارهای با ثبات یا نوسانی، ممکن است در نهایت به نتیجه برسند، اما تعداد گام‌های مورد نیاز برای رسیدن به این حالت، ممکن است بسیار زیاد باشد، حتی اگر الگوی پایه نسبتاً ساده باشد. تغییرات محلی بر روی الگوی پایه ممکن است به صورت نامحدودی منتشر گردد. ولفرم تخمین زده‌است که اگر نگوییم همه، بسیاری از اتوماتاهای سلولی کلاس ۴، قادر به انجام محاسبات جهانی می‌باشند. این مسئله برای ۱۱۰ قانون و بازی زندگی مطرح شده توسط کانوی، اثبات گردیده‌است.

این تعاریف در طبیعت به صورت کیفی بوده و فضاهایی به منظور تفسیر آن وجود دارد. بر اساس نظریه ولفرم، "... با تقریباً هر الگوی طبق بندی عمومی، موارد اجتناب ناپذیری وجود دارند که به یک کلاس با یک تعریف و به کلاس دیگر با تعریف دیگری اختصاص داده می‌شوند؛ بنابراین این مسئله در اتوماتای سلولی وجود دارد که: قانون‌های وابسته موقعیتی وجود دارند که برخی ویژگی‌های یک کلاس و برخی ویژگی‌های کلاس دیگری را نمایش می‌دهند. طبقه‌بندی مطرح شده توسط ولفرم، به صورت تجربی با یک خوشه بندی از خروجی طول فشرده اتوماتای سلولی منطبق است.

با الهام از طبقه‌بندی مطرح شده توسط ولفرم تلاش‌های متعددی به منظور طبقه‌بندی اوتاماتای سلولی در کلاس‌های فرمال دقیق وجود داشته‌است. به عنوان نمونه، کولیک و یو سه کلاس خوش تعریف (و یک کلاس چهارمی برای اتوماتا که با هیچ‌کدام از این‌ها منطبق نیست) را مطرح نمودند. این کلاس‌ها برخی اوقات با نام کلاس‌های کولیک-یو نام برده می‌شوند. به اثبات رسیده‌است که عضویت در این کلاس‌ها تصمیم ناپذیر است. کلاس ۲ طبقه‌بندی ولفرم را می‌توان به دو زیرگروه قانون‌های با ثبات (ثابت) و نوسانی (پریودیک) تقسیم‌بندی نمود.

برگشت‌پذیر

یک اتوماتای سلولی معکوس پذیر است اگر برای هر پیکربندی جاری اتوماتای سلولی، دقیقاً یک پیکربندی قبلی (پیش تصویر) وجود داشته باشد. اگر یک تفکر در مورد اتوماتای سلولی این باشد که یک تابع به منظور نگاشت پیکربندی به پیکربندی است، به صورت معکوس پذیر نشان می‌دهد که این تابع یک به یک است. اگر یک اتوماتای سلولی معکوس پذیر باشد، رفتار زمان معکوس آن نیز می‌تواند به عنوان یک اتوماتای سلولی توصیف گردد. این حقیقت از نتایج قضیه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) که در رابطه با ویژگی‌های توپولوژیکال اتوماتای سلولی است، می‌باشد. برای اتوماتای سلولی که در آن هر پیکربندی یک پیش تصویر ندارد، پیکربندی‌های بدون پیش تصویر الگوهای پیوسته و متراکم ادن (به انگلیسی: Garden of Eden) نامیده می‌شوند.

برای اتوماتای تک بعدی، الگوریتم‌های شناخته شده‌ای به منظور تشخیص معکوس‌پذیری با معکوس ناپذیری یک قانون وجود دارد. با این حال، برای اتوماتای‌های دو بعدی یا چند بعدی معکوس‌پذیری تصمیم ناپذیر است، بدین معنا که، الگوریتم وجود ندارد که به عنوان ورودی یک قانون اتوماتا دریافت نموده و تضمین کند که می‌تواند به صورت درستی معکوس‌پذیری آن را تعیین نماید. اثبات مطرح شده توسط جارکو کری به مشکل کاش کاری موجود در مدل ونگ تایلز مرتبط است.

اتوماتای سلولی معکوس پذیر، اغلب به منظور شبیه‌سازی پدیده‌های فیزیکی مانند مباحث حرکتی گاز و مایع مورد استفاده قرار می‌گیرد. زیرا آن‌ها از قوانین ترمودینامیک پیروی می‌کنند. چنین اتوماتای سلولی قانون‌هایی دارد که به صورت ویژه به گونه‌ای ساخته شده‌اند که معکوس پذیر باشد. چنین سیستم‌هایی توسط نرمن مارگولس و توماس توفولی و دیگران مورد مطالعه قرار گرفته‌است. تکنیک‌های متعددی می‌تواند به منظور ساخت صریح اتوماتای سلولی معکوس پذیر با معکوس‌های شناخته شده، مورد استفاده قرار بگیرد. دو نوع متداول از این تکنیک‌ها، اتوماتای سلولی مرتبه دوم (به انگلیسی: second order cellular automaton) و اتوماتای سلولی بلاکی (به انگلیسی: block cellular automaton) می‌باشند. هر دو این‌ها بیانگر تعریف‌هایی از طرق مختلف برای یک اتوماتای سلولی هستند. هرچند چنین اتوماتایی تعریف بیان شده در بالا را کاملاً برآورده نمی‌کند، می‌تواند نشان دهد که آن‌ها می‌توانند با اتوماتای سلولی متعارف با تعداد همسایگی و تعداد حالت‌های به اندازه کافی بزرگ شبیه‌سازی شوند، و بنابراین می‌تواند به عنوان زیرمجموعه‌ای از اتوماتای سلولی متعارف مطرح گردد. به‌طور عکس، می‌تواند نشان داده شود که هر اتوماتای سلولی معکوس‌پذیری می‌تواند با یک اتوماتای سلولی بلاکی شبیه‌سازی شود.

تک گرایی

یک کلاس خاص از اتوماتای سلولی، اتوماتای سلولی تک گرایی (به انگلیسی: Totalistic) است. حالت هر سلول در اتوماتای سلولی تک گرا به وسیله یک عدد نشان داده می‌شود. (معمولاً یک عدد صحیح گرفته شده از یک مجموعه متناهی)، و مقدار یک سلول در زمان t فقط به مجموع مقادیر سلول‌های موجود در همسایگی آن در زمان t-1 بستگی دارد. (احتمالاً از جمله خود آن سلول). اگر حالت سلول در زمان t به مقدار خودش در زمان t-1 وابسته باشد، این اتوماتای سلولی، تک گرای خارجی نامیده می‌شود. بازی زندگی مطرح شده توسط کانوی یک نمونه از اتوماتای فوق با مقادیر ۰ و ۱ برای سلول‌ها است. اتوماتای سلولی تک گرای خارجی با ساختار همسایگی از نوع مور، مشابه با زندگی برخی اوقات اتوماتای سلولی زندگی مانند نامیده می‌شود.

اتوماتای مرتبط

تعمیم‌های زیادی برای مفهوم اتوماتای سلولی امکان‌پذیر است. یک راه استفاده از چیز دیگری به جای شبکه چهارخانه است. (مکعبی و غیره) به عنوان مثال، وقتی طرح کاشی با شش ضلعی‌های منظم است، این شش گوشه‌ها می‌توانند به عنوان سلول مورد استفاده قرار بگیرند. در بسیاری از موارد، اتوماتای سلولی حاصل شده، با اتوماتاهایی با شبکه چهار خانه با طراحی خاص همسایگی و قانون‌ها، برابری می‌کند. نوع دیگر می‌تواند پیاده‌سازی نامنظم خود شبکه باشد، به عنوان مثال مدل پنروس تایل (به انگلیسی: Penrose tiling).

یک اتوماتای سلولی مبتنی بر سلول‌های شش گوش. (قانون ۳۴/۲)

همچنین، قانون‌ها نیز می‌توانند احتمالی باشد به جای آنکه قطعی باشند. چنین اتوماتای سلولی، اتوماتای سلولی احتمالی نامیده می‌شوند. قانون‌های احتمالی، به هر الگو در زمان t، احتمالاتی به منظور گذر از سلول مرکزی به هر حالت ممکن در زمان t+1 اختصاص می‌دهند. برخی اوقات، یک قانون ساده‌تر مورد استفاده قرار می‌گیرد. به عنوان مثال: «بازی زندگی یک قانون است، اما برای هر گام زمانی احتمال ۰٫۰۰۱٪ وجود دارد که هر سلول به رنگ مخالف خود گذر داشته باشد».

همسایگی یا قانون‌ها می‌توانند در طول زمان یا مکان تغییر کنند. به عنوان مثال، در ابتدا، حالت جدید یک سلول می‌تواند توسط سلول‌های افقی مجاور تعیین گردد، اما برای توسعه بعدی می‌تواند سلول‌های عمودی مورد استفاده قرار بگیرد.

در اتوماتای سلولی، حالت جدید سلول، تحت تأثیر حالت جدید سلول‌های دیگر نمی‌باشد. این موضوع می‌تواند تغییر کند، به گونه‌ای که، به عنوان نمونه، یک بلاک دو در دو از سلول‌ها می‌تواند توسط خود آن سلول و سول‌های مجاورش تعیین گردد.

اتوماتاهای پیوسته نیز وجود دارد. این‌ها شبیه اتوماتای سلولی تک گرا هستند، اما به جای اینکه قانون‌ها و حالت‌ها به صورت گسسته (به عنوان مثال، یک جدول که از حالت‌های {۰٬۱٬۲}) باشند، توابع پیوسته مورد استفاده قرار می‌گیرد، و حالت‌ها به صورت پیوسته می‌شوند. (معمولاً مقادیری در بازه [۰٬۱]) و حالت‌های مکان، یک تعداد متناهی از اعداد حقیقی می‌باشد. اتوماتاهای سلولی خاصی می‌توانند بر اساس الگوهای شناور مانند این عمل نمایند.

اتوماتای فضایی پیوسته، یک رشته پیوسته از مکان‌ها دارد. حالت یک مکان یک تعداد متناهی از یک مجموعه اعداد حقیقی است. زمان هم به صورت پوسته بوده و حالت با توجه به معادلات دیفرانسیل تکامل می‌یابد. یک نمونه مهم، ساختارهای واکنش-انتشار می‌باشد، معادلات دیفرانسیلی که توسط تورینگ به منظور توضیح نحوه ایجاد هاشور در خرها و نحوه ایجاد نقاط در پلنگ توسط واکنش‌های شیمیایی معرفی شد. زمانی که این‌ها توسط اتوماتای سلولی تقریب زده شده، آن‌ها اغلب بر اساس الگوهای مشابه‌ای عمل می‌کنند. مک لنان، اتوماتای فضایی پیوسته را به عنوان یک مدل محاسباتی در نظر می‌گیرد.

مثال‌های شناخته شده‌ای برای اتوماتای فضایی پیوسته وجود دارد که پدیده انتشار را مشابه گلایدرهای در بازی زندگی نمایش می‌دهند.

ماشین‌های سلولی ابتدایی

ساده‌ترین اتوماتای سلولی مهم می‌تواند یک بعدی، با دو حالت امکان‌پذیر برای هر سلول، که همسایه‌ها، سلول‌های مجاور در دو طرف آن تعریف می‌شود، می‌باشد. یک سلول و دو همسایه آن، همسایگی از سه سلول را می‌سازند؛ بنابراین ۸ الگوی ممکن برای همسایگی وجود دارد. یک قانون شامل تصمیم‌گیری برای هر الگوست که تعیین می‌کند در توسعه بعدی سلول باید ۰ باشد یا ۱.

بر این اساس ۲۵۶ قانون امکان‌پذیر وجود دارد. این ۲۵۶ اتوماتای سلولی به‌طور کلی بر اساس کد ولفرم آن‌ها (یک قرارداد نامگذاری استاندارد که توسط ولفرم مطرح شد. این استاندارد به هر قانون یک عدد از ۰ تا ۲۵۵ تخصیص می‌دهد) ارجاع داده می‌شوند. تعدادی از مقالات به تحلیل و مقایسه این ۲۵۶ اتوماتای سلولی پرداخته‌اند. اتوماتای سلولی قانون ۳۰ و ۱۱۰ رولی به‌طور خاص، جالب هستند. تصویر زیر، سابقه هر کدام را زمانی که پیکر بندی آغازین شامل یک ۱ (در قسمت بالای هر تصویر) که توسط ۰ها احاطه شده‌است، نشان می‌دهد. هر ردیف از پیکس‌ها، یک توسعه را در سابقه اتوماتا نشان می‌دهد، t=۰ بالاترین ردیف می‌باشد. هر پیکسل ۰ با رنگ سفید و هر پیکسل ۱ با رنگ سیاه، رنگ آمیزی شده‌است.

اتوماتای سلولی ۳۰ قانونی

اتوماتای سلولی ۱۱۰ قانونی

مدل ۳۰ قانونه رفتار کلاس ۳ را نمایش می‌دهد. بدین معنا که الگوهای ساده مشابه آنچه نشان داده شده، منجر به ایجاد سوابقی بی نظرم و ظاهراً تصادفی می‌گردند. مدل ۱۱۰ قانونه، مشابه بازی زندگی، چگونگی رفتار چیزی که ولفرم آن را کلاس ۴ نامیده‌است را نشان می‌دهد که رفتاری نه کاملاً تصادفی و نه کاملاً تکراری دارند. ساختارهای محلی ظاهر می‌شوند و از راه‌های جستجوی پیچیده مختلف با یکدیگر تعامل می‌کنند. در طی توسعه کتاب جنبه جدید از علوم، همانطوری‌که دستیار تحقیقاتی ولفرم در سال ۱۹۹۴، متیو کوک اثبات نموده بود که برخی از این ساختارها به اندازه کافی قوی هستند که بتواند جامعیت (عمومیت) را پشتیبانی کنند. این نتیجه جالب است زیرا ۱۱۰ قانونه یک سیستم تک بعدی کاملاً ساده و سیستمی است که برای یک مهندس انجام چنین رفتار خاصی مشکل است.

بنابراین این نتیجه حمایت قابل توجهی را برای دیدگاه ولفرم که سیستم‌های کلاس ۴، به نظر می‌رسد به‌طور ذاتی یک سیستم جهانی باشند، فراهم آورد. کوک اثبات خود را در یک کنفرانس اتوماتای سلولی مؤسسه سنتا فه در سال ۱۹۹۸ مطرح نمود اما ولفرم مانع از قرارگیری این اثبات در مجموعه مقالات کنفرانس گردید. زیرا ولفرم نمی‌خواست که پیش از انتشار کتاب جنبه جدید از علوم این اثبات انتشار پیدا کند. در سال ۲۰۰۴، اثبات کوک سرانجام در ژورنال ولفرم (سری ۱۵، شماره ۱) منتشر شد، ده سال پس از زمانی که کوک آن را مطرح نموده بود. ۱۱۰ قانونه شامل پایه‌هایی می‌شود که برخی از کوچکترین ماشین‌های تورینگ جهانی بر اساس آن ساخته شده‌اند.

فضای قانون

قانون ابتدایی اتوماتای سلولی، توسط ۸ بیت مشخص شده‌است، و همه قانون‌های ابتدایی اتوماتای سلولی می‌توانند بر روی روئوس یک واحد ابر مکعب هشت بعدی در نظر گرفته شوند. این واحد ابر مکعب فضای قانون اتوماتای سلولی می‌باشد. برای نزدیکترین همسایه بعدی اتوماتای سلولی، یک قانون با ۳۲ بیت مشخص می‌گردد، و فضای قانون اتوماتای سلولی یک واحد ابرمکعب ۳۲ بعدی می‌باشد. فاصله میان دو قانون، می‌تواند به وسیله تعداد گام‌های مورد نیاز برای حرکت از یک راس، که قانون اول را مشخص می‌کند، به راس دیگر، که قانون دیگر را مشخص می‌کند، در امتداد لبه ابر کعب، مشخص شود. این فاصله قانون تا قانون همچنین فاصله همینگ نیز نامیده می‌شود.

فضای قانون اتوماتای سلولی به ما اجازه می‌دهد که بپرسیم آیا قانون‌هایی با رفتار پویای مشابه در نزدیکی هم قرار دارند یا خیر. از نظر گرافیکی، ترسیم یک ابر مکعب با تعداد بعد زیاد، در یک صفحه دو بعدی یک کار دشوار باقی مانده‌است، و یک مکان‌یاب خام یک قانون در ابرمکعب، بیت شماره ۱ در میان رشته ۸ بیتی مربوط به قانون مقدماتی (و یا رشته ۳۲ بیتی برای قانون‌های نزدیکترین همسایه بعدی) می‌باشد. ترسیم قانون‌ها در کلاس مختلف مدل ولفرم در این چنین برش‌هایی از فضای قانون، نشان می‌دهد که قانون‌های کلاس ۱، متمایل به داشتن تعداد کمتری از بیت ۱ هستند، در نتیجه در یک ناحیه از فضا قرار دارند. در حالی که قانون‌های کلاس ۳، تمایل به داشتن تعداد بیت ۱ با نسبتی بیشتر از ۵۰ درصد دارند.

برای فضای قانون‌های بزرگتر اتوماتای سلولی، نشان داده شده‌است که قانون‌های کلاس ۴، در موقعیتی بین کلاس ۱ و ۳ قرار گرفته‌اند. این مشاهدات پایه و اساس اصطلاح کناره‌های بی نظمی و یادآور انتقال فاز در ترمودینامیک می‌باشد.

زیست‌شناسی

یک الگوی اتوماتای سلولی را در سطح خود نمایش می‌دهد.

برخی از فرایندهای زیستی بر اساس اتوماتای سلولی اتفاق افتاده یا می‌توانند شبیه‌سازی شوند. الگوی برخی از صدف‌ها، شبیه صدف‌های نوع کانوس و سیمبیولا، توسط اتوماتای سلولی طبیعی تولید شده‌اند. سلول‌های رنگدانه‌ای در یک نوار باریک در لبه پوسته آن‌ها قرار دارند. هر سلول با پیروی از یک نسخه طبیعی از قوانین ریاضی، با توجه به فعال یا غیرفعال بودن سلول‌های رنگدانه‌ای همسایه‌اش، رنگدانه ترشح می‌کند. نوار سلول الگوی رنگی را همانطوری‌که پوسته یه آرامی در حال رشد است، بر روی آن قرار می‌دهد. به عنوان مثال، گونه گسترده‌تر کانوس، یک الگوی مشابه با اتوماتای ۳۰ قانونه مدل ولفرم را دربردارد.

گیاهان مصرف و از دست دادن گازها (بخارها) را از طریق یک مکانیزم ماشین سلولی تنظیم می‌نمایند. هر روزنه در برگ به عنوان یک سلول عمل می‌کند.

الگوهای امواج متحرک بر روی سطح سفالوپودها را می‌توان با یک اتوماتای سلولی دو بعدی دو حالته شبیه‌سازی نمود. هر حالت بر اساس یک کراماتوفر توسعه یافته یا لغو شده‌است.

اتوماتای آستانه‌ای به منظور شبیه‌سازی نورون‌ها ایجاد گردید و با به‌کارگیری آن رفتارهای پیچیده مانند شناخت و یادگیری قابل شبیه‌سازی می‌باشد.

فیبروبلاستها شباهت‌هایی با اتوماتای سلولی دارند، بدین صورت که هر فیبروبلاست فقط با همسایگان خود تعامل دارد.

انواع شیمیایی

واکنش بلوسوف-ژابوتینسکی یک اوسیلاتور شیمیایی فضا-زمانی است که می‌تواند با روش‌های اتوماتای سلولی شبیه‌سازی شود. در دهه ۵۰ میلادی، ژابوتینسکی، (کار بلوسوف را گسترش داد) کشف کرد که هنگامی که یک لایه همگن نازک از مخلوطی از مالونیک اسید، برمات اسیدی و نمک سریک با هم مخلوط شده و در سکون قرار داده می‌شوند، طرح‌های هندسی جذاب مانند دایره متحد المرکز و مارپیچی در سراسر آن منتشر می‌شوند. الکساندر ددنی، در بخش "Computer Recreations" از شماره آگوست سال ۱۹۸۸ مجله ساینتیفیک آمریکن، یک ماشین سلولی که توسط که توسط مارتین گرهارد و هایک شوستر از دانشگاه بیلفد (آلمان غربی) توسعه داده شد مورد بحث قرار داد. این اتوماتا الگوهای موجی شبیه آنچیزی که در واکنش بلوسوف-ژابوتینسکی است، تولید می‌نماید.

کاربردها

پردازنده‌های کامپیوتر

پردازنده‌های اتوماتای سلولی پیاده‌سازی فیزیکی مفاهیم CA هستند، که می‌تواند اطلاعات را از بعد محاسباتی پردازش نماید. مؤلفه‌های پردازش‌ها در یک شبکه منظم از سلول‌های یکسان سازماندهی شده‌اند. این شبکه معمولاً یک کاشی کاری مربعی، یا موزاییک کاری، از دو یا سه بعد می‌باشد. سایر انواع کاشی کاری نیز امکان‌پذیر است ولی هنوز مورد استفاده قرار نگرفته‌است. حالت‌های سلول فقط به وسیله تعامل آن با همسایگان مجاورش مشخص می‌شود. هیچ راهی برای برقراری ارتباط مستقیم با سلول‌های دورتر وجود ندارد. یکی از نمونه‌های چنین پردازنده اتوماتای سلولی پیکربندی آرایه، آرایه‌های سیستولیک می‌باشد. تعاملات سلولی می‌تواند از طریق بار الکتریکی، مغناطیس؛ ارتعاشات (فونون در مقیاس کوانتومی) یا هر روش فیزیکی دیگری انجام پذیرد. این مسئله می‌تواند از طرق مختلفی انجام گیرد بنابراین هیچ اتصال سیمی میان مؤلفه‌ها نیاز نیست. این پردازنده با پردازنده‌هایی که امروزه در بیشتر کامپیوترها مورد استفاده قرار می‌گیرند (طراحی ون نیومن) کاملاً متفاوت است. در طراحی ون نیومن، پردازنده به بخش‌ها به همراه مؤلفه‌هایی تقسیم شده‌است که می‌توانند با مؤلفه‌های راه دور از طریق سیم‌ها، ارتباط برقرار نمایند.

رمز نویسی

مدل ۳۰ قانونه در اصل به عنوان یک رمزگذار بلوکی امکان‌پذیر برای استفاده در رمزگذاری قطعه‌ای پیشنهاد گردید. اتوماتای سلولی دو بعدی برای تولید عدد تصادفی مورد استفاده قرار گرفته‌است. اتوماتای سلولی برای رمزنگاری کلید عمومی ارائه شده‌است. تابع یک طرفه، تکامل یک CA متناهی است که یافتن معکوس آن به نظر دشوار می‌رسد. با توجه به قانون، هر کسی می‌تواند به راحتی حالت‌های آینده را محاسبه نماید، اما به نظر می‌رسد که محاسبه حالت‌های قبلی بسیار دشوار باشد.

کدهای تصحیح خطا

مدل اتوماتای سلولی (به انگلیسی: CA) به منظور طراحی کدهای تصحیح خطا در مقاله "Design of CAECC – Cellular Automata Based Error Correcting Code" مورد استفاده قرار گرفته‌است. این مقاله یک طرح جدید از ساختن کدهای همینگ SEC-DED با استفاده از CA را توصیف نموده‌است؛ و همچنین گزارشی از یک رمزگشای سخت‌افزاری سریع نیز در این مقاله آمده‌است.

مدل‌سازی واقعیت‌های فیزیکی

همانگونه که آندر ایلاچینسکی در اتوماتای سلولی خود اشاره نمود، بسیاری از محققین این سؤال را مطرح نموده‌اند که آیا جهان یک اتوماتای سلولی است. او استدلال می‌کند که اهمیت این سؤال ممکن است با یک مشاهده ساده، بهتر مشخص گردد، این مشاهده می‌تواند به شرح زیر بیان گردد.

سیر تکاملی ۱۰ قانونه را در نظر بگیرید: اگر این قانون یک نوع فیزیک خارج از بعد باشد، توصیف مناسب الگوهای مشاهده شده چه خواهد بود؟ اگر یک ناظر نداند که چگونه تصاویر تولید شده‌است، او ممکن است در نهایت بتواند حدس‌هایی در مورد حرکت برخی اشیای ذره مانند بیان نماید. یک فیزیکدان به نام جیمز کراچفیلد بر مبنای این ایده یک تئوری ریاضی دقیق مطرح نمود که پیدایش آماری از ذرات، از اتوماتای سلولی را اثبات می‌کند. در آن زمان، همانگونه که این استدلال به پیش می‌رود، مسئله تعجب‌آور می‌تواند این باشد که جهان که در حال حاضر به وسیله فیزیک و با اشیای ذره مانند (فیزیک ذرات) توصیف می‌شود، می‌تواند یک اتوماتای سلولی در پایه ای‌ترین سطح آن باشد. در حالی که تئوری کامل در این زمنیه همچنان در حال توسعه است؛ توسعه این فرضیه، محققان را بر آن داشت که حدس و گمان‌های جالب و شهودهای مثمر ثمری را در زمینه چگونگی قابل درک بودن جهان در یک چارچوب گسسته مطرح نمایند. ماروین مینسکی یکی از پیشگامان هوش مصنوعی، به بررسی چگونگی درک نحوه تعامل ذرات با شبکه اتوماتای سلولی چهار بعدی پرداخت؛ کنراد تسوزه مخترع اولین کامپیوتر، Z3، یک شبکه منظم به منظور بررسی پرسشی مبنی بر محتوای اطلاعاتی ذرات، مطرح نمود. اخیراً ادوارد فردکین، چیزی را که خودش «فرضیه طبیعت محدود» می‌نامد را به نمایش گذاشت. به عنوان مثال، این ایده که در نهایت هر کمیت فیزیکی، از جمله فضا و زمان، به کیمیت‌هایی گسسته و محدود تبدیل خواهد شد. فردکین و ولفرم از طرفداران سر سخت فیزیک مبتنی بر اتوماتای سلولی هستند.

در سال‌های اخیر، پیشنهادهای دیگری در این زمینه، در میان مقالات مرتبط با محاسبات غیر استاندارد مطرح گردید. کتاب جنبه دیگری از علوم، اتوماتای سلولی را به عنوان کلیدی برای درک مسایل مختلف شامل فیزیک، در نظر گرفته‌است. ریاضیات مدلی بر اساس منابع (به انگلیسی: Mathematics of the Models of Reference)، یک جهان اصلی دو بعدی /سه بعدی مبتنی بر یک شبکه «لوزی دوازده وجهی» جدید و یک قانون منحصر به فرد را نشان داد. این مدل عمومیت (جامعیت) را تأمین نموده (این مدل با ماشین تورینگ برابری می‌کند)، معکوس‌پذیری را کامل نموده (یک ضرورت که اگر کسی خواست بتواند کمیت‌های متعددی را ذخیره کند و اطلاعات از بین نرود) و در نظریه مرتبه اول گنجانده شده‌است که اجازه محاسبه عبارات کیفی در مورد تکامل جهان را داده‌است.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Cellular automaton». در دانشنامهٔ ویکی‌پدیای انگلیسی.