موضوع مقاله: اتوماتای سلولی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اتوماتای سلولی | مقدمه: قاب|چپ| الگوهای منظم گاسپرن گلایدرهای منظمی را برای بازی زندگی کانوی می‌سازند اتوماتای سلولی مدلی از ریاضیات گسسته است که در مباحثی چون نظریه محاسبه‌پذیری، ریاضیات، فیزیک، سامانه‌های انطباقی پیچیده، زیست‌شناسی نظری و ریز ساختارها مورد مطالعه قرار گرفته‌است. | ## بخش 1: اتوماتای سلولی | اتوماتای سلولی با نام‌هایی مانند فضاهای سلولی، اتوماتای مفروش سازی، ساختارهای همگن، ساختارهای سلولی، ساختارهای مفروش سازی و آرایه‌های تکرار شونده نیز بیان می‌گردد. یک اتوماتای سلولی شامل یک شبکه منظم از سلول‌ها است که هر کدام از آن‌ها در یکی از حالات از مجموعه حالات متناهی امکان‌پذیر قرار دارند. مانند on و offیا مقدار منطقی 0 و 1.همچنین شبکه می‌تواند هر بعد متناهی داشته باشد. برای هر سلول، یک مجموعه از سلول‌ها که همسایهٔ آن نامیده می‌شود، نسبت به آن سلول مشخص تعریف شده‌است. یک حالت آغازین (time = ۰)یا(t=0) با تخصیص دادن یک وضعیت به هر سلول انتخاب می‌شود. یک نسل جدید (توسعه t به وسیله ۱)، بر اساس یکسری قوانین ثابت (عموماً یک تابع ریاضی) که وضعیت جدید برای هر سلول را بر اساس وضعیت جاری آن سلول و وضعیت‌های سلول‌های همسایه آن، مشخص می‌کند، تولید می‌شود. به‌طور معمول، قوانین به روزرسانی وضعیت سلول‌ها برای هر سلول مشابه است و در طول زمان تغییر نمی‌کند، و به کل شبکه به صورت هم‌زمان اعمال خواهد شد، هر چند استثناهایی نیز وجود دارد، مانند اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام. این مفهوم در ابتدا در دهه ۴۰ میلادی، به وسیله استنی‌سواف اولام و جان فون نویمان در حالی که آن‌ها در آزمایشگاه ملی لس آلاموس بودند، کشف شد. این موضوع در دهه ۵۰ و ۶۰ میلادی نیز توسط برخی مورد مطالعه قرار گرفت ولی تا دهه ۷۰ و مطرح شدن بازی زندگی کانوی، یک اتوماتای سلولی دو بعدی، که علاقه به این موضوع را به ابعادی فراتر از بحث‌های دانشگاهی گسترش داد، هنوز وجود نداشت. در دهه ۸۰، استیون ولفرم، که درگیر مطالعه سیستماتیک یک اتوماتای تک بعدی یا چیزی که او اتوماتای سلولی بنیادی می‌نامید، بود، دستیار تحقیقاتی او متیو کوک نشان داد که یکی از این قوانین، کامل بودن تورینگ است. از جمله آن‌ها می‌توان به کاربرد آن در پردازنده‌های کامپیوتری و رمزنگاری اشاره کرد. طبقه‌بندی اولیهٔ اتوماتای سلولی که توسط ولفرم اشاره گردید از ۱ تا ۴ شماره‌گزاری شده‌است. این طبقه‌بندی‌ها به ترتیب بدین صورت هستند: اتوماتایی که در آن الگوها به‌طور کلی به صورت همگن تثبیت شده‌اند، اتوماتایی که الگوها در آن به ساختارهای اغلب نوسانی یا با ثبات توسعه یافته‌اند، اتوماتایی که در آن الگوها در آن به یک قالب ظاهراً بی نظم توسعه یافته‌اند و اتوتایی که در آن الگوها کاملاً پیچیده شده‌اند و ممکن است برای مدت زمان طولانی به همراه ساختارهای محلی با ثبات، باقی بمانند. این طبقه آخر به نظر می‌رسد از منظر کامل بودن تورینگ صحیح بوده یا قادر به شبیه‌سازی یک ماشین تورینگ باشد. انواع خاص از اتوماتای سلولی این‌ها هستند که برگشت‌پذیر هستند که در آن فقط یک پیکربندی مستقیماً به … بعدی منجر می‌شود، و توتالیستیک هستند که در آن مقدار آیندهٔ سلول‌های منفرد به ارزش کل یک گروه از سلول‌های همسایه بستگی دارد. اتوماتای سلولی می‌تواند انواع گوناگونی از سیستم‌های دنیای واقعی شامل سیستم‌های زیستی و شیمیایی را شبیه‌سازی کند. هر مربع یک «سلول» نامیده می‌شود و برای هر سلول دو حالت امکان‌پذیر است، سیاه و سفید. دو نوع از رایج‌ترین انواع همسایه‌ها، همسایه‌های فون نویمان و همسایه‌های مور هستند. مدل اول، پس از مطرح شدن نظریه‌پرداز اتوماتای سلولی، شامل چهار سلول تعامد (جبر خطی)، نامگذاری شد. مدل دوم شامل همسایه نوع فون نویمان هست و علاوه بر آن چهار سلول باقی‌مانده در اطراف سلولی که باید حالتش محاسبه شود را نیز شامل می‌گردد. برای هر یک از ۵۱۲ الگوی امکان‌پذیر، جدول قوانین مشخص خواهد کرد که حالت سلول مرکزی در فاصله زمانی بعدی سیاه یا سفید خواهد بود. یک مدل رایج دیگر از انواع همسایه، همسایه مدل فون نویمان بسط یافته‌است که شامل دو نزدیک‌ترین سلول در هر جهت متعامد، برای کل هشت خانه، می‌باشد. معادله عمومی برای چنین سیستمی از قوانین، k به قوه k به قوه s می‌باشد که K در آن تعداد حالت‌های ممکن برای یک سلول و S تعداد سلول‌های همسایه (از جمله خود سلولی مورد نظر) که به منظور تعیین حالت بعدی سلول مورد استفاده قرار می‌گیرد؛ بنابراین در یک سیستم دوبعدی با همسایه از نوع مور، تعداد کل اتوماتای ممکن برابر است با229, یا. اغلب فرض می‌شود همه سلول‌ها در جهان از یک حالت یکسان شروع می‌شوند، به جز برای تعداد متناهی سلول در حالت‌های دیگر؛ فرایند تخصیص مقادیر به حالت‌ها پیکربندی نامیده می‌شود. به‌طور کلی، گاهی اوقات فرض می‌شود جهان در آغاز با یک الگوی تناوبی پوشش داده شده‌است و فقط تعداد متناهی از سلول‌ها از این الگو پیروی نمی‌کند. مشکل مشاهده شده در مورد شبکه‌های محدود این است که چگونه سلول‌ها را در گوشه‌ها مدیریت نماییم. یکی متد امکان‌پذیر این است که اجازه دهیم مقادیر در این سلول‌ها ثابت باقی بمانند. یک متد دیگر می‌تواند این باشد که همسایه را برای این‌گونه سلول‌ها به گونه‌ای متفاوت تعریف نماییم. ممکن است یک نفر بیان کند که این سلول‌ها همسایه‌های کمتری دارند، اما در این صورت مجبور به تعریف قوانین جدیدی برای سلول‌های موجود در گوشه‌ها خواهیم بود. این می‌تواند بدین صورت تصویرسازی شود که گوشه‌ها چپ و راست چهارگوش را به یکدیگر متصل نموده و یک تیوپ ایجاد نماییم، سپس بالا و پایین گوشه‌های تیوپ را به یکدیگر متصل نموده و یک چنبره (شکلی همانند حلقه) ایجاد نماییم. این کار به منظور حل مشکل حدود مرزی در همسایگی‌ها انجام شده‌است، اما یک مزیت دیگر این سیستم این است که به راحتی توسط توابع هم‌نهشتی (نظریه اعداد) قابل برنامه‌ریزی است. به عنوان مثال، در یک اتوماتای سلولی تک بعدی، مانند مثال زیر، همسایگی سلول xit برابر است با {xi−1t−1, xit−1, xi+1t−۱}، که t گام‌های زمانی (قایم)، و i ایندکس (افقی) در یک گسترش می‌باشد. در همان زمان، جان فون نویمان، همکار اولام در لس آلاموس، بر روی مشکلات سیستم‌های خود تکرار یا همان خودجایگزین‌گری کار می‌کرد. در روند توسعه این طراحی، ون نیمن متوجه مشکل بزرگی در زمینه ساخت یک روبات خود تکرار شد، و هزینه بالای در تولید ربات به همراه دریایی از قطعات که برای ساخت تکرارش نیاز دارد نیز از دیگر مشکلات است. نیومن یک مقاله با عنوان «نظریه منطقی و عمومی اتوماتا» در سال ۱۹۴۸ در نشست هیگزون مطالعه کرد. اولام کسی بود که پیشنهاد استفاده از یک سیستم گسسته برای ایجاد یک مدل کاهش یافته از مدل خود تکرار را مطرح نمود. نیلز آل باریچرلی بسیاری از کشفیات اولیه در زمینه این مدل‌های زندگی مصنوعی را انجام داده‌است. اولام و ون نیومن یک متد به منظور محاسبه حرکت مایع در اواخر دهه ۵۰ میلادی ایجاد نمودند. مفهوم مؤثر این متد در نظر گرفتن مایع به عنوان گروهی از واحدهای گسسته و محاسبه حرکت هر کدام بر اساس رفتار همسایگان خود بوده‌است. همانند شبکه توری منظم اولام، اتوماتای سلولی طراحی شده توسط ون نیومن به صورت دو بعدی با الگوریتم خود تکرار او پیاده‌سازی شده‌است. نتیجه یک سازنده کپی‌کننده جهانی که با یک اتوماتای سلولی و مجموعه کوچکی از همسایگان. (فقط این سلول‌هایی که با آن‌ها در تماس هستند به عنوان همسایه محسوب می‌شوند، برای اتوماتای سلولی مدل ون نیون، فقط سلول‌های متعامد) و ۲۹ حالت برای هر سلول، بود. ون نیومن یک نظریه اثبات وجود مطرح نمود که یک الگوی مشخص، یک کپی بی پایان از خود را درون جهان سلولی داده شده به وسیله طراحی پیکره بندی ۲۰۰۰۰۰ سلول که بتوانند چنین کاری انجام دهند، ایجاد خواهد نمود. این طراحی با عنوان مدل موزائیک‌کاری شناخته شده‌است و با نام سازنده جهانی ون نیومن نامیده می‌شود. همچنین در دهه ۴۰ میلادی، نوربرت وینر و آرتور رونزبلاس یک مدل از رسانه‌های تحریک پذیر را با به‌کارگیری برخی ویژگی‌های یک اتوماتای سلولی توسعه دادند. با این وجود مدل آن‌ها یک اتوماتای سلولی نیست زیرا حداقل، انتشار سیگنال در آن پیوسته و جبهه‌های موج به صورت منحنی است. یک مدل اتاماتای سلولی صحیح از رسانه تحریک پذیر توسط گرینبرگ و هستینگ در سال ۱۹۷۸ توسعه یافته و مورد مطالعه قرار گرفت. کار اصلی وینر و رونزبلاس شامل نگرش‌های مختلفی است و همچنان در نشریان مدرن تحقیقاتی در زمینه بی نظمی قلبی و سیستم‌های تحریک پذیر مطرح می‌باشد. در دهه ۶۰ میلادی اتوماتای سلولی به عنوان بخش مشخصی از سیستم پویا مورد مطالعه قرار گرفت و اتصال آن با مبحث ریاضیاتی از پویایی سمبلیک برای اولین بار محقق گردید. چیزی که هنوز هم به عنوان یک مقاله اصلی برای مطالعه ریاضیاتی اتوماتای سلولی در نظر گرفته می‌شود. اساسی‌ترین نتیجه، در توصیف ویژگی‌های نظریه کورتیس-هدلند-لیندون در مورد اینکه مجموعه قوانین سراسری اتوماتای سلولی به عنوان مجموعه‌ای از درون دگرگونی‌های پیوسته از فضای تغییر است. در سال ۱۹۶۹، پیشگام کامپیوتر آلمانی، کنراد تسوزه، کتاب خود را با عنوان فضای محاسبه منتشر نمود. او در این کتاب مطرح نموده‌است که قوانین فیزیکی جهان توسط طبیعت گسسته شده‌است، و کل جهان خروجی یک محاسبه قطعی در یک ماشین سلولی منفرد است. در دهه ۷۰ میلادی، یک اتوماتای سلولی دو حالتهٔ دوبعدی با نام بازی زندگی به صورت گسترده‌ای شناخته شد، بخصوص در انجمن‌های محاسباتی اولیه. این اوتوماتا توسط جان کانوی اختراع و توسط مارتین گاردنر در مقاله علمی آمریکایی به شهرت رسید. قوانین آن به صورت زیر است: اگر یک سلول دارای دو بلاک همسایه باشد، به همان صورت قبل باقی می‌ماند. بر خلاف سادگی آن، سیستم به تنوع قابل توجهی در رفتار دست پیدا خواهد نمود، که در حال نوسان به صورت رندوم ظاهری یا منظم هست. یکی از آشکاراترین ویژگی‌های بازی زندگی رخ دادن تکرار شوندهٔ گلایدرها (ترتیبی از سلول‌ها که بنا به ضرورت خودشان را در شبکه جابجا می‌کنند) است. | ## بخش 2: اتوماتای سلولی | این امکان‌پذیر است که به گونه‌ای اتوماتا را سازماندهی نماییم که گلایدرها به منظور انجام محاسبات با یکدیگر تعامل داشته باشند، و پس از تلاش‌های زیاد، این نشان داده شد که بازی زندگی می‌تواند با یک تورینگ ماشین جهانی برابری نماید. این مسئله به عنوان یک موضوع تفریحی تصور شده و کارهای بسیار کمی خارج از چارچوب بررسی خصوصیات بازی زندگی و اندک قوانین مرتبط با آن در دهه ۷۰ میلادی انجام پذیرفت. استیون ولفرم به صورت مستقل کار بر روی اتوماتای سلولی را در اوسط سال ۱۹۸۱، پس از بررسی الگوهای پیچیده در طبیعت و نحوه شکل‌گیری آن‌ها بر خلاف قانون دوم ترمودینامیک، آغاز نمود. تحقیقات او در ابتدا با تمرکز بر روی سیستم‌های مدلسازی مانند سیستم‌های عصبی آغاز شده بود. پیچیدگی غیرقابل انتظار در رفتار چنین قانون‌هایی، ولفرم را به این جهت سوق داد که به این موضوع شک کند که پیچیدگی موجود در طبیعت نیز ناشی از مکانیزم مشابه‌ای باشد. با این وجود، تحقیقات او موجب شد، او دریابد که اتوماتای سلولی سیستم مدلسازی ضعیفی به منظور مدلسازی سیستم‌های عصبی محسوب می‌شود. علاوه بر این، در طی این همین زمان، ولفرم مفاهیم ذاتاً تصادفی بودن و تقلیل ناپذیری را فرموله بندی نموده و پیشنهاد داد که اتوماتای ۱۱۰ قانونه ممکن است همگانی باشد - این حقیقت بعداً توسط متیو کوک، دستیار تحقیقاتی ولفرم، در سال ۱۹۹۰ اثبات گردید. در این متن، ولفرم در مورد اینکه اکتشافات انجام شده در زمینه اتوماتای سلولی حقایق مجزا و منحصر به فردی نیستند ولی قدرتمند بوده و برای همهٔ رشته‌های علمی پراهمیت هستند، استدلال‌های گسترده‌ای را مطرح نمود. علی‌رغم سردرگمی زیاد مطبوعات، این کتاب در مورد نظریه اساسی فیزیک مبتنی بر اتوماتای سلولی استدلالی مطرح نمی‌نماید. هر چند این کتاب تعداد کمی از مدل‌های خاص فیزیکی مبتنی بر اتوماتای سلولی را توصیف می‌نماید و همچنین مدل‌هایی مبتنی بر سیستم‌های انتزاعی با کیفیت‌های متفاوت، ارائه می‌نماید. طبقه‌بندی ولفرم، در کتاب جنبه جدید از علوم و مقالات بسیاری در سال‌های مربوط به اواسط دهه ۸۰ میلادی، چهار کلاس را در زمینه چگونگی تقسیم‌بندی اتوماتای سلولی و بسیاری از مدل‌های ساده محاسباتی دیگر بر اساس رفتارشان، توصیف نمود. در حالی که مطالعات قبلی در زمینه اتوماتای سلولی، به منظور تعیین نمودن انواع الگوها برای هر قانون مشخص بود، طبقه‌بندی مطرح شده توسط ولفرم، اولین تلاش در زمینه طبقه‌بندی خود قوانین بود. به ترتیب پیچیدگی، این کلاس‌های بدین شرح می‌باشند: کلاس اول: تقریباً تمام الگوهای پایه که به سرعت به یک حالت همگن و با ثبات توسعه می‌یابند. کلاس دوم: تقریباً تمام الگوهای پایه که به سرعت به یک ساختار با ثبات یا نوسانی توسعه می‌یابند. برخی از موارد تصادفی، در این الگوی پایه در نظر گرفته نمی‌شود اما برخی از آن‌ها نیز لحاظ می‌گردد. کلاس سوم: تقریباً تمام الگوهای اولیه که به صورت شبه تصادفی و بی نظم توسعه می‌یابند. هرگونه ساختار با ثباتی که ظاهر شوند به سرعت توسط نویزهای اطراف از بین خواهند رفت. کلاس چهارم: تقریباً تمام الگوهای اولیه که به ساختارهایی با روش‌های پیچیده و جالب تعامل و با شکل‌گیری ساختارهای محلی که قادر به زنده ماندن برای مدت طولانی هستند، توسعه پیدا می‌کنند. کلاس نوع دوم، ساختارهای با ثبات یا نوسانی، ممکن است در نهایت به نتیجه برسند، اما تعداد گام‌های مورد نیاز برای رسیدن به این حالت، ممکن است بسیار زیاد باشد، حتی اگر الگوی پایه نسبتاً ساده باشد. ولفرم تخمین زده‌است که اگر نگوییم همه، بسیاری از اتوماتاهای سلولی کلاس ۴، قادر به انجام محاسبات جهانی می‌باشند. با تقریباً هر الگوی طبق بندی عمومی، موارد اجتناب ناپذیری وجود دارند که به یک کلاس با یک تعریف و به کلاس دیگر با تعریف دیگری اختصاص داده می‌شوند؛ بنابراین این مسئله در اتوماتای سلولی وجود دارد که: قانون‌های وابسته موقعیتی وجود دارند که برخی ویژگی‌های یک کلاس و برخی ویژگی‌های کلاس دیگری را نمایش می‌دهند. طبقه‌بندی مطرح شده توسط ولفرم، به صورت تجربی با یک خوشه بندی از خروجی طول فشرده اتوماتای سلولی منطبق است. با الهام از طبقه‌بندی مطرح شده توسط ولفرم تلاش‌های متعددی به منظور طبقه‌بندی اوتاماتای سلولی در کلاس‌های فرمال دقیق وجود داشته‌است. به عنوان نمونه، کولیک و یو سه کلاس خوش تعریف (و یک کلاس چهارمی برای اتوماتا که با هیچ‌کدام از این‌ها منطبق نیست) را مطرح نمودند. کلاس ۲ طبقه‌بندی ولفرم را می‌توان به دو زیرگروه قانون‌های با ثبات (ثابت) و نوسانی (پریودیک) تقسیم‌بندی نمود. برگشت‌پذیر یک اتوماتای سلولی معکوس پذیر است اگر برای هر پیکربندی جاری اتوماتای سلولی، دقیقاً یک پیکربندی قبلی (پیش تصویر) وجود داشته باشد. اگر یک تفکر در مورد اتوماتای سلولی این باشد که یک تابع به منظور نگاشت پیکربندی به پیکربندی است، به صورت معکوس پذیر نشان می‌دهد که این تابع یک به یک است. اگر یک اتوماتای سلولی معکوس پذیر باشد، رفتار زمان معکوس آن نیز می‌تواند به عنوان یک اتوماتای سلولی توصیف گردد. این حقیقت از نتایج قضیه کورتیس-هدلند-لیندون که در رابطه با ویژگی‌های توپولوژیکال اتوماتای سلولی است، می‌باشد. برای اتوماتای سلولی که در آن هر پیکربندی یک پیش تصویر ندارد، پیکربندی‌های بدون پیش تصویر الگوهای پیوسته و متراکم ادن نامیده می‌شوند. برای اتوماتای تک بعدی، الگوریتم‌های شناخته شده‌ای به منظور تشخیص معکوس‌پذیری با معکوس ناپذیری یک قانون وجود دارد. با این حال، برای اتوماتای‌های دو بعدی یا چند بعدی معکوس‌پذیری تصمیم ناپذیر است، بدین معنا که، الگوریتم وجود ندارد که به عنوان ورودی یک قانون اتوماتا دریافت نموده و تضمین کند که می‌تواند به صورت درستی معکوس‌پذیری آن را تعیین نماید. اثبات مطرح شده توسط جارکو کری به مشکل کاش کاری موجود در مدل ونگ تایلز مرتبط است. اتوماتای سلولی معکوس پذیر، اغلب به منظور شبیه‌سازی پدیده‌های فیزیکی مانند مباحث حرکتی گاز و مایع مورد استفاده قرار می‌گیرد. چنین اتوماتای سلولی قانون‌هایی دارد که به صورت ویژه به گونه‌ای ساخته شده‌اند که معکوس پذیر باشد. چنین سیستم‌هایی توسط نرمن مارگولس و توماس توفولی و دیگران مورد مطالعه قرار گرفته‌است. تکنیک‌های متعددی می‌تواند به منظور ساخت صریح اتوماتای سلولی معکوس پذیر با معکوس‌های شناخته شده، مورد استفاده قرار بگیرد. دو نوع متداول از این تکنیک‌ها، اتوماتای سلولی مرتبه دوم و اتوماتای سلولی بلاکی می‌باشند. هرچند چنین اتوماتایی تعریف بیان شده در بالا را کاملاً برآورده نمی‌کند، می‌تواند نشان دهد که آن‌ها می‌توانند با اتوماتای سلولی متعارف با تعداد همسایگی و تعداد حالت‌های به اندازه کافی بزرگ شبیه‌سازی شوند، و بنابراین می‌تواند به عنوان زیرمجموعه‌ای از اتوماتای سلولی متعارف مطرح گردد. به‌طور عکس، می‌تواند نشان داده شود که هر اتوماتای سلولی معکوس‌پذیری می‌تواند با یک اتوماتای سلولی بلاکی شبیه‌سازی شود. (معمولاً یک عدد صحیح گرفته شده از یک مجموعه متناهی)، و مقدار یک سلول در زمان t فقط به مجموع مقادیر سلول‌های موجود در همسایگی آن در زمان t-1 بستگی دارد. اگر حالت سلول در زمان t به مقدار خودش در زمان t-1 وابسته باشد، این اتوماتای سلولی، تک گرای خارجی نامیده می‌شود. بازی زندگی مطرح شده توسط کانوی یک نمونه از اتوماتای فوق با مقادیر ۰ و ۱ برای سلول‌ها است. اتوماتای سلولی تک گرای خارجی با ساختار همسایگی از نوع مور، مشابه با زندگی برخی اوقات اتوماتای سلولی زندگی مانند نامیده می‌شود. (مکعبی و غیره) به عنوان مثال، وقتی طرح کاشی با شش ضلعی‌های منظم است، این شش گوشه‌ها می‌توانند به عنوان سلول مورد استفاده قرار بگیرند. در بسیاری از موارد، اتوماتای سلولی حاصل شده، با اتوماتاهایی با شبکه چهار خانه با طراحی خاص همسایگی و قانون‌ها، برابری می‌کند. نوع دیگر می‌تواند پیاده‌سازی نامنظم خود شبکه باشد، به عنوان مثال مدل پنروس تایل . (قانون ۳۴/۲) همچنین، قانون‌ها نیز می‌توانند احتمالی باشد به جای آنکه قطعی باشند. قانون‌های احتمالی، به هر الگو در زمان t، احتمالاتی به منظور گذر از سلول مرکزی به هر حالت ممکن در زمان t+1 اختصاص می‌دهند. به عنوان مثال: «بازی زندگی یک قانون است، اما برای هر گام زمانی احتمال ۰٫۰۰۱٪ وجود دارد که هر سلول به رنگ مخالف خود گذر داشته باشد». به عنوان مثال، در ابتدا، حالت جدید یک سلول می‌تواند توسط سلول‌های افقی مجاور تعیین گردد، اما برای توسعه بعدی می‌تواند سلول‌های عمودی مورد استفاده قرار بگیرد. این موضوع می‌تواند تغییر کند، به گونه‌ای که، به عنوان نمونه، یک بلاک دو در دو از سلول‌ها می‌تواند توسط خود آن سلول و سول‌های مجاورش تعیین گردد. این‌ها شبیه اتوماتای سلولی تک گرا هستند، اما به جای اینکه قانون‌ها و حالت‌ها به صورت گسسته (به عنوان مثال، یک جدول که از حالت‌های {۰٬۱٬۲ باشند، توابع پیوسته مورد استفاده قرار می‌گیرد، و حالت‌ها به صورت پیوسته می‌شوند. (معمولاً مقادیری در بازه [۰٬۱ و حالت‌های مکان، یک تعداد متناهی از اعداد حقیقی می‌باشد. یک نمونه مهم، ساختارهای واکنش-انتشار می‌باشد، معادلات دیفرانسیلی که توسط تورینگ به منظور توضیح نحوه ایجاد هاشور در خرها و نحوه ایجاد نقاط در پلنگ توسط واکنش‌های شیمیایی معرفی شد. زمانی که این‌ها توسط اتوماتای سلولی تقریب زده شده، آن‌ها اغلب بر اساس الگوهای مشابه‌ای عمل می‌کنند. مثال‌های شناخته شده‌ای برای اتوماتای فضایی پیوسته وجود دارد که پدیده انتشار را مشابه گلایدرهای در بازی زندگی نمایش می‌دهند. ماشین‌های سلولی ابتدایی ساده‌ترین اتوماتای سلولی مهم می‌تواند یک بعدی، با دو حالت امکان‌پذیر برای هر سلول، که همسایه‌ها، سلول‌های مجاور در دو طرف آن تعریف می‌شود، می‌باشد. | ## بخش 3: اتوماتای سلولی | یک سلول و دو همسایه آن، همسایگی از سه سلول را می‌سازند؛ بنابراین ۸ الگوی ممکن برای همسایگی وجود دارد. یک قانون شامل تصمیم‌گیری برای هر الگوست که تعیین می‌کند در توسعه بعدی سلول باید ۰ باشد یا ۱. این ۲۵۶ اتوماتای سلولی به‌طور کلی بر اساس کد ولفرم آن‌ها (یک قرارداد نامگذاری استاندارد که توسط ولفرم مطرح شد. تصویر زیر، سابقه هر کدام را زمانی که پیکر بندی آغازین شامل یک ۱ (در قسمت بالای هر تصویر) که توسط ۰ها احاطه شده‌است، نشان می‌دهد. هر ردیف از پیکس‌ها، یک توسعه را در سابقه اتوماتا نشان می‌دهد، t=۰ بالاترین ردیف می‌باشد. بدین معنا که الگوهای ساده مشابه آنچه نشان داده شده، منجر به ایجاد سوابقی بی نظرم و ظاهراً تصادفی می‌گردند. مدل ۱۱۰ قانونه، مشابه بازی زندگی، چگونگی رفتار چیزی که ولفرم آن را کلاس ۴ نامیده‌است را نشان می‌دهد که رفتاری نه کاملاً تصادفی و نه کاملاً تکراری دارند. ساختارهای محلی ظاهر می‌شوند و از راه‌های جستجوی پیچیده مختلف با یکدیگر تعامل می‌کنند. در طی توسعه کتاب جنبه جدید از علوم، همانطوری‌که دستیار تحقیقاتی ولفرم در سال ۱۹۹۴، متیو کوک اثبات نموده بود که برخی از این ساختارها به اندازه کافی قوی هستند که بتواند جامعیت (عمومیت) را پشتیبانی کنند. این نتیجه جالب است زیرا ۱۱۰ قانونه یک سیستم تک بعدی کاملاً ساده و سیستمی است که برای یک مهندس انجام چنین رفتار خاصی مشکل است. بنابراین این نتیجه حمایت قابل توجهی را برای دیدگاه ولفرم که سیستم‌های کلاس ۴، به نظر می‌رسد به‌طور ذاتی یک سیستم جهانی باشند، فراهم آورد. کوک اثبات خود را در یک کنفرانس اتوماتای سلولی مؤسسه سنتا فه در سال ۱۹۹۸ مطرح نمود اما ولفرم مانع از قرارگیری این اثبات در مجموعه مقالات کنفرانس گردید. زیرا ولفرم نمی‌خواست که پیش از انتشار کتاب جنبه جدید از علوم این اثبات انتشار پیدا کند. در سال ۲۰۰۴، اثبات کوک سرانجام در ژورنال ولفرم (سری ۱۵، شماره ۱) منتشر شد، ده سال پس از زمانی که کوک آن را مطرح نموده بود. ۱۱۰ قانونه شامل پایه‌هایی می‌شود که برخی از کوچکترین ماشین‌های تورینگ جهانی بر اساس آن ساخته شده‌اند. فضای قانون قانون ابتدایی اتوماتای سلولی، توسط ۸ بیت مشخص شده‌است، و همه قانون‌های ابتدایی اتوماتای سلولی می‌توانند بر روی روئوس یک واحد ابر مکعب هشت بعدی در نظر گرفته شوند. برای نزدیکترین همسایه بعدی اتوماتای سلولی، یک قانون با ۳۲ بیت مشخص می‌گردد، و فضای قانون اتوماتای سلولی یک واحد ابرمکعب ۳۲ بعدی می‌باشد. فاصله میان دو قانون، می‌تواند به وسیله تعداد گام‌های مورد نیاز برای حرکت از یک راس، که قانون اول را مشخص می‌کند، به راس دیگر، که قانون دیگر را مشخص می‌کند، در امتداد لبه ابر کعب، مشخص شود. فضای قانون اتوماتای سلولی به ما اجازه می‌دهد که بپرسیم آیا قانون‌هایی با رفتار پویای مشابه در نزدیکی هم قرار دارند یا خیر. از نظر گرافیکی، ترسیم یک ابر مکعب با تعداد بعد زیاد، در یک صفحه دو بعدی یک کار دشوار باقی مانده‌است، و یک مکان‌یاب خام یک قانون در ابرمکعب، بیت شماره ۱ در میان رشته ۸ بیتی مربوط به قانون مقدماتی (و یا رشته ۳۲ بیتی برای قانون‌های نزدیکترین همسایه بعدی) می‌باشد. ترسیم قانون‌ها در کلاس مختلف مدل ولفرم در این چنین برش‌هایی از فضای قانون، نشان می‌دهد که قانون‌های کلاس ۱، متمایل به داشتن تعداد کمتری از بیت ۱ هستند، در نتیجه در یک ناحیه از فضا قرار دارند. در حالی که قانون‌های کلاس ۳، تمایل به داشتن تعداد بیت ۱ با نسبتی بیشتر از ۵۰ درصد دارند. برای فضای قانون‌های بزرگتر اتوماتای سلولی، نشان داده شده‌است که قانون‌های کلاس ۴، در موقعیتی بین کلاس ۱ و ۳ قرار گرفته‌اند. این مشاهدات پایه و اساس اصطلاح کناره‌های بی نظمی و یادآور انتقال فاز در ترمودینامیک می‌باشد. برخی از فرایندهای زیستی بر اساس اتوماتای سلولی اتفاق افتاده یا می‌توانند شبیه‌سازی شوند. الگوی برخی از صدف‌ها، شبیه صدف‌های نوع کانوس و سیمبیولا، توسط اتوماتای سلولی طبیعی تولید شده‌اند. هر سلول با پیروی از یک نسخه طبیعی از قوانین ریاضی، با توجه به فعال یا غیرفعال بودن سلول‌های رنگدانه‌ای همسایه‌اش، رنگدانه ترشح می‌کند. نوار سلول الگوی رنگی را همانطوری‌که پوسته یه آرامی در حال رشد است، بر روی آن قرار می‌دهد. به عنوان مثال، گونه گسترده‌تر کانوس، یک الگوی مشابه با اتوماتای ۳۰ قانونه مدل ولفرم را دربردارد. گیاهان مصرف و از دست دادن گازها (بخارها) را از طریق یک مکانیزم ماشین سلولی تنظیم می‌نمایند. الگوهای امواج متحرک بر روی سطح سفالوپودها را می‌توان با یک اتوماتای سلولی دو بعدی دو حالته شبیه‌سازی نمود. اتوماتای آستانه‌ای به منظور شبیه‌سازی نورون‌ها ایجاد گردید و با به‌کارگیری آن رفتارهای پیچیده مانند شناخت و یادگیری قابل شبیه‌سازی می‌باشد. فیبروبلاستها شباهت‌هایی با اتوماتای سلولی دارند، بدین صورت که هر فیبروبلاست فقط با همسایگان خود تعامل دارد. انواع شیمیایی واکنش بلوسوف-ژابوتینسکی یک اوسیلاتور شیمیایی فضا-زمانی است که می‌تواند با روش‌های اتوماتای سلولی شبیه‌سازی شود. در دهه ۵۰ میلادی، ژابوتینسکی، (کار بلوسوف را گسترش داد) کشف کرد که هنگامی که یک لایه همگن نازک از مخلوطی از مالونیک اسید، برمات اسیدی و نمک سریک با هم مخلوط شده و در سکون قرار داده می‌شوند، طرح‌های هندسی جذاب مانند دایره متحد المرکز و مارپیچی در سراسر آن منتشر می‌شوند. این اتوماتا الگوهای موجی شبیه آنچیزی که در واکنش بلوسوف-ژابوتینسکی است، تولید می‌نماید. کاربردها پردازنده‌های کامپیوتر پردازنده‌های اتوماتای سلولی پیاده‌سازی فیزیکی مفاهیم CA هستند، که می‌تواند اطلاعات را از بعد محاسباتی پردازش نماید. یکی از نمونه‌های چنین پردازنده اتوماتای سلولی پیکربندی آرایه، آرایه‌های سیستولیک می‌باشد. تعاملات سلولی می‌تواند از طریق بار الکتریکی، مغناطیس؛ ارتعاشات (فونون در مقیاس کوانتومی) یا هر روش فیزیکی دیگری انجام پذیرد. این مسئله می‌تواند از طرق مختلفی انجام گیرد بنابراین هیچ اتصال سیمی میان مؤلفه‌ها نیاز نیست. این پردازنده با پردازنده‌هایی که امروزه در بیشتر کامپیوترها مورد استفاده قرار می‌گیرند (طراحی ون نیومن) کاملاً متفاوت است. در طراحی ون نیومن، پردازنده به بخش‌ها به همراه مؤلفه‌هایی تقسیم شده‌است که می‌توانند با مؤلفه‌های راه دور از طریق سیم‌ها، ارتباط برقرار نمایند. رمز نویسی مدل ۳۰ قانونه در اصل به عنوان یک رمزگذار بلوکی امکان‌پذیر برای استفاده در رمزگذاری قطعه‌ای پیشنهاد گردید. با توجه به قانون، هر کسی می‌تواند به راحتی حالت‌های آینده را محاسبه نماید، اما به نظر می‌رسد که محاسبه حالت‌های قبلی بسیار دشوار باشد. این مقاله یک طرح جدید از ساختن کدهای همینگ SEC-DED با استفاده از CA را توصیف نموده‌است؛ و همچنین گزارشی از یک رمزگشای سخت‌افزاری سریع نیز در این مقاله آمده‌است. مدل‌سازی واقعیت‌های فیزیکی همانگونه که آندر ایلاچینسکی در اتوماتای سلولی خود اشاره نمود، بسیاری از محققین این سؤال را مطرح نموده‌اند که آیا جهان یک اتوماتای سلولی است. او استدلال می‌کند که اهمیت این سؤال ممکن است با یک مشاهده ساده، بهتر مشخص گردد، این مشاهده می‌تواند به شرح زیر بیان گردد. سیر تکاملی ۱۰ قانونه را در نظر بگیرید: اگر این قانون یک نوع فیزیک خارج از بعد باشد، توصیف مناسب الگوهای مشاهده شده چه خواهد بود؟ اگر یک ناظر نداند که چگونه تصاویر تولید شده‌است، او ممکن است در نهایت بتواند حدس‌هایی در مورد حرکت برخی اشیای ذره مانند بیان نماید. یک فیزیکدان به نام جیمز کراچفیلد بر مبنای این ایده یک تئوری ریاضی دقیق مطرح نمود که پیدایش آماری از ذرات، از اتوماتای سلولی را اثبات می‌کند. در آن زمان، همانگونه که این استدلال به پیش می‌رود، مسئله تعجب‌آور می‌تواند این باشد که جهان که در حال حاضر به وسیله فیزیک و با اشیای ذره مانند (فیزیک ذرات) توصیف می‌شود، می‌تواند یک اتوماتای سلولی در پایه ای‌ترین سطح آن باشد. در حالی که تئوری کامل در این زمنیه همچنان در حال توسعه است؛ توسعه این فرضیه، محققان را بر آن داشت که حدس و گمان‌های جالب و شهودهای مثمر ثمری را در زمینه چگونگی قابل درک بودن جهان در یک چارچوب گسسته مطرح نمایند. ماروین مینسکی یکی از پیشگامان هوش مصنوعی، به بررسی چگونگی درک نحوه تعامل ذرات با شبکه اتوماتای سلولی چهار بعدی پرداخت؛ کنراد تسوزه مخترع اولین کامپیوتر، Z3، یک شبکه منظم به منظور بررسی پرسشی مبنی بر محتوای اطلاعاتی ذرات، مطرح نمود. اخیراً ادوارد فردکین، چیزی را که خودش «فرضیه طبیعت محدود» می‌نامد را به نمایش گذاشت. به عنوان مثال، این ایده که در نهایت هر کمیت فیزیکی، از جمله فضا و زمان، به کیمیت‌هایی گسسته و محدود تبدیل خواهد شد. در سال‌های اخیر، پیشنهادهای دیگری در این زمینه، در میان مقالات مرتبط با محاسبات غیر استاندارد مطرح گردید. کتاب جنبه دیگری از علوم، اتوماتای سلولی را به عنوان کلیدی برای درک مسایل مختلف شامل فیزیک، در نظر گرفته‌است. | ## جمع‌بندی | این مدل عمومیت (جامعیت) را تأمین نموده (این مدل با ماشین تورینگ برابری می‌کند)، معکوس‌پذیری را کامل نموده (یک ضرورت که اگر کسی خواست بتواند کمیت‌های متعددی را ذخیره کند و اطلاعات از بین نرود) و در نظریه مرتبه اول گنجانده شده‌است که اجازه محاسبه عبارات کیفی در مورد تکامل جهان را داده‌است.