ک اتوماتای سلولی یک مدلی از ریاضیات گسسته می باشد که در مباحثی چون نظریه رایانش‌پذیری ، ریاضیات ، فیزیک ، سامانه‌های انطباقی پیچیده ، زیست شناسی نظری و ریز ساختار ها مورد مطالعه قرار گرفته است. اتوماتای سلولی با نام هایی مانند فضاهای سلولی ، اتوماتای مفروش سازی ، ساختار های همگن ، ساختارهای سلولی ، ساختارهای مفروش سازی و آرایه های تکرار شونده نیز بیان می گردد.
یک اتوماتای سلولی شامل یک شبکه منظم از سلول ها است که هر کدام از آن ها در یکی از حالات از مجموعه حالات متناهی امکان پذیر قرار دارند. مانند on و off . شبکه می تواند هر بعد متناهی داشته باشد. برای هر سلول ، یک مجموعه از سلول ها که همسایه ی آن نامیده می شود ، نسبت به آن سلول مشخص تعریف شده است. یک حالت آغازین (time t = 0) با تخصیص دادن یک وضعیت به هر سلول انتخاب می شود. یک نسل جدید (توسعه t به وسیله 1) ، بر اساس یکسری قوانین ثابت (عموما یک تابع ریاضی) که وضعیت جدید برای هر سلول را بر اساس وضعیت جاری آن سلول و وضعیت های سلول های همسایه آن ، مشخص می کند ، تولید می شود. به طور معمول ، قوانین به روز رسانی وضعیت سلول ها برای هر سلول مشابه است و در طول زمان تغییر نمی کند ، و به کل شبکه بصورت همزمان اعمال خواهد شد ، هر چند استثناهایی نیز وجود دارد ، مانند اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام.
این مفهوم در ابتدا در دهه 40 میلادی ، به وسیله استنی‌سواف اولام و جان فون نویمان در حالی که آنها در آزمایشگاه ملی لس آلاموس بودند ، کشف شد. این موضوع در دهه 50 و 60 میلادی نیز توسط برخی مورد مطالعه قرار گرفت ولی تا دهه 70 و مطرح شدن بازی زندگی کانوی ، یک اتوماتای سلولی دو بعدی ، که علاقه به این موضوع را به ابعادی فراتر از بحث های دانشگاهی گسترش داد ، هنوز وجود نداشت. در دهه 80 ، استیون ولفرم ، که درگیر مطالعه سیستماتیک یک اتوماتای تک بعدی یا چیزی که او اتوماتای سلولی بنیادی می نامید ، بود ، دستیار تحقیقاتی او متیو کوک نشان داد که یکی از این قوانین ، کامل بودن تورینگ است. ولفرم مقاله ای با عنوان جنبه دیگری از علوم (به انگلیسی: A New Kind of Science) را در سال 2002 منتشر نمود. او در این مقاله مدعی شد اتوماتای سلولی در بسیاری از حوزه های علوم کاربرد دارد . از جمله آن ها می توان به کاربرد آن در پردازنده های کامپیوتری و رمزنگاری اشاره کرد.
طبقه بندی اولیه ی اتوماتای سلولی که توسط ولفرم اشاره گردید از 1 تا 4 شماره گزاری شده است. این طبقه بندی ها به ترتیب بدین صورت هستند : اتوماتایی که در آن الگوها به طور کلی به صورت همگن تثبیت شده اند ، اتوماتایی که الگوها در آن به ساختار های اغلب نوسانی یا با ثبات توسعه یافته اند ، اتوماتایی که در آن الگوها در آن به یک قالب ظاهرا بی نظم توسعه یافته اند و اتوتایی که در آن الگوها کاملا پیچیده شده اند و ممکن است برای مدت زمان طولانی به همراه ساختار های محلی با ثبات ، باقی بمانند. این طبقه آخر به نظر می رسد از منظر کامل بودن تورینگ صحیح بوده و یا قادر به شبیه سازی یک ماشین تورینگ باشد. انواع خاص از اتوماتای سلولی این ها هستند که بر گشت پذیر هستند که در آن فقط یک پیکربندی مستقیما به .... بعدی منجر می شود ، و توتالیستیک هستند که در آن مقدار آبنده ی سلول های منفرد به ارزش کل یک گروه از سلول های همسایه بستگی دارد. اتوماتای سلولی می تواند انواع گوناگونی از سیستم های دنیای واقعی شامل سیستم های زیستی و شیمیایی را شبیه سازی کند.
چکیده
یک چنبره، یک شکل چنبره ای
یک راه برای شبیه سازی اتوماتای سلولی دو بعدی ، استفاده از تعداد متناهی صفحات کاغذ میلیمتری به همراه مجموعه از قوانین برای سلول ها می باشد. هر مربع یک "سلول" نامیده می شود و برای هر سلول دو حالت امکان پذیر است ، سیاه و سفید. همسایه های سلول نزدیکترین و معمولا سلول های مجاور آن هستند. دو نوع از رایج ترین انواع همسایه ها ، همسایه های ون نیومن و همسایه های مور هستند. مدل اول ، پس از مطرح شدن نظریه پرداز اتوماتای سلولی ، شامل چهار سلول تعامد (جبر خطی) ، نامگذاری شد. مدل دوم شامل همسایه نوع ون نیومن هست و علاوه بر آن چهار سلول باقی مانده در اطراف سلولی که باید حالتش محاسبه شود را نیز شامل می گردد. برای یک چنین سلولی و همسایه نوع مور آن ، 512 الگوی امکان پذیر وجود دارد. برای هر یک از 512 الگوی امکان پذیر ، جدول قوانین مشخص خواهد کرد که حالت سلول مرکزی در فاصله زمانی بعدی سیاه یا سفید خواهد بود. بازی زندگی کانوی یک نسخه محبوب و عمومی از این مدل است. یک مدل رایج دیگر از انواع همسایه ، همسایه مدل ون نیومن بسط یافته است که شامل دو نزدیک ترین سلول در هر جهت متعامد ، برای کل هشت خانه ، می باشد. معادله عمومی برای چنین سیستمی از قوانین ، k به قوه k به قوه s می باشد که K در آن تعداد حالت های ممکن برای یک سلول و S تعداد سلول های همسایه (از جمله خود سلولی مورد نظر) که به منظور تعیین حالت بعدی سلول مورد استفاده قرار میگیرد. بنابراین در یک سیستم دوبعدی با همسایه از نوع مور ، تعداد کل اتوماتای ممکن برابر است با229, یا۱.۳۴×۱۰۱۵۴. اغلب فرض می شود همه سلول ها در جهان از یک حالت یکسان شروع می شوند ، به جز برای تعداد متناهی سلول در حالت های دیگر ؛ فرآیند تخصیص مقادیر به حالت ها پیکربندی نامیده می شود. به طور کلی ، گاهی اوقات فرض می شود جهان در آغاز با یک الگوی تناوبی پوشش داده شده است و فقط تعداد متناهی از سلول ها از این الگو پیروی نمیکند. فرض دوم در اتوماتای سلولی یک بعدی رایج است.
اتوماتای سلولی اغلب بر روی شبکه متناهی شبیه سازی می شود تا یک شبکه نامتناهی. در حالت دو بعدی ، جهان باید بصورت چهارگوش باشد بجای یک صفحه نامتناهی. مشکل مشاهده شده در مورد شبکه های محدود این است که چگونه سلول ها را در گوشه ها مدیریت نماییم. نحوه مدیریت آن ها بر روی مقادیر همه ی سلول ها در شبکه تاثیر گزار خواهد بود. یکی متد امکان پذیر این است که اجازه دهیم مقادیر در این سلول ها ثابت باقی بمانند. یک متد دیگر می تواند این باشد که همسایه را برای اینگونه سلول ها به گونه ای متفاوت تعریف نماییم. ممکن است یک نفر بیان کند که این سلول ها همسایه های کمتری دارند ، اما در این صورت مجبور به تعریف قوانین جدیدی برای سلول های موجود در گوشه ها خواهیم بود. این سلول ها معمولا با یک ترتیب toroidal مدیریت می شوند. این میتواند بدین صورت تصویر سازی شود که گوشه ها چپ و راست چهارگوش را به یکدیگر متصل نموده و یک تویوپ ایجاد نماییم ، سپس بالا و پایین گوشه های تیوپ را به یکدیگر متصل نموده و یک چنبره (شکلی همانند حلقه) ایجاد نماییم. فضاهای مربوط به سایر ابعاد به شیوه ای مشابه مدیرت می شوند. این کار به منظور حل مشکل حدود مرزی در همسایگی ها انجام شده است ، اما یک مزیت دیگر این سیستم این است که به راحتی توسط توابع هم‌نهشتی (نظریه اعداد) قابل برنامه ریزی است. به عنوان مثال ، در یک اتوماتای سلولی تک بعدی ، مانند مثال زیر ، همسایگی سلول xit برابر است با {xi−1t−1, xit−1, xi+1t−1} ، که t گام های زمانی (قایم) ، و i ایندکس (افقی) در یک گسترش می باشد.
تاریخچه
جان فون نویمان، نشان شناسایی در آزمایشگاه ملی لس آلاموس
استنی‌سواف اولام ، زمانی که در آزمایشگاه ملی لس آلاموس ، در دهه 40 میلادی مشغول به کار بود ، بر روی رشد کریستال ها با به کارگیری یک مدل شبکه توری منظم به عنوان مدل خود، مطالعه مینمود. در همان زمان ، جان فون نویمان ، همکار اولام در لس آلاموس ، بر روی مشکلات سیستم های خود تکرار یا همان خودجایگزین‌گری کار میکرد. طراحی اولیه ون نیومن بر اساس ساخته شدن یک ربات توسط یک ربات دیگر بنا نهاده شد. این طراحی به عنوان مدل حرکتی شناخته می شود. در روند توسعه این طراحی ، ون نیمن متوجه مشکل بزرگی در زمینه ساخت یک روبات خود تکرار شد ، و هزینه بالای در تولید ربات به همراه دریایی از قطعات که برای ساخت تکرارش نیاز دارد نیز از دیگر مشکلات است. نیومن یک مقاله با عنوان "نظریه منطقی و عمومی اتوماتا" در سال 1948 در نشست هیگزون مطالعه کرد. اولام کسی بود که پیشنهاد استفاده از یک سیستم گسسته برای ایجاد یک مدل کاهش یافته از مدل خود تکرار را مطرح نمود. نیلز آل باریچرلی بسیاری از کشفیات اولیه در زمینه این مدل های زندگی مصنوعی را انجام داده است.
اولام و ون نیومن یک متد به منظور محسابه حرکت مایع در اوخر دهه 50 میلادی ایجاد نمودند. مفهوم موثر این متد در نظر گرفتن مایع به عنوان گروهی از واحد های گسسته و محاسبه حرکت هر کدام بر اساس رفتار همسایگان خود بوده است. بدین سان اولین سیستم اتوماتای سلولی متولد شد. همانند شبکه توری منظم اولام ، اتوماتای سلولی طراحی شده توسط ون نیومن بصورت دو بعدی با الگوریتم خود تکرار او پیاده سازی شده است. نتیجه یک سازنده کپی کننده جهانی که با یک اتوماتای سلولی و مجموعه کوچکی از همسایگان.(فقط این سلول هایی که با آن ها در تماس هستند به عنوان همسایه محسوب می شوند ، برای اتوماتای سلولی مدل ون نیون ، فقط سلول های متعامد ) و 29 حالت برای هر سلول ، بود. ون نیومن یک نظریه اثبات وجود مطرح نمود که یک الگوی مشخص ، یک کپی بی پایان از خود را درون جهان سلولی داده شده به وسیله طراحی پیکره بندی 200000 سلول که بتوانند چنین کاری انجام دهند ، ایجاد خواهد نمود. این طراحی با عنوان مدل موزائیک‌کاری (به انگلیسی: Tessellation) شناخته شده است و با نام سازنده جهانی ون نیومن نامیده میشود.
همچنین در دهه 40 میلادی ، نوربرت وینر و آرتور رونزبلاس یک مدل از رسانه های تحریک پذیر را با به کارگیری برخی ویژگی های یک اتوماتای سلولی توسعه دادند. انگیزه اصلی آن ها ، توصیف ریاضی انتقال ضربه در سیستم های قلبی بود. با این وجود مدل آن ها یک اتوماتای سلولی نیست زیرا حداقل ، انتشار سیگنال در آن پیوسته و جبهه های موج بصورت منحنی است. یک مدل اتاماتای سلولی صحیح از رسانه تحریک پذیر توسط گرینبرگ و هستینگ در سال 1978 توسعه یافته و مورد مطالعه قرار گرفت. کار اصلی وینر و رونزبلاس شامل نگرش های مختلفی است و همچنان در نشریان مدرن تحقیقاتی در زمینه بی نظمی قلبی و سیستم های تحریک پذیر مطرح می باشد.
در دهه 60 میلادی اتوماتای سلولی به عنوان بخش مشخصی از سیستم پویا مورد مطاله قرار گرفت و اتصال آن با مبحث ریاضیاتی از پویایی سمبلیک برای اولین بار محقق گردید. در سال 1969 ، هدلند نتایج زیادی را مبتنی بر همین دیدگاه گردآوری نمود. چیزی که هنوز هم به عنوان یک مقاله اصلی برای مطالعه ریاضیاتی اتوماتای سلولی در نظر گرفته می شود. اساسی ترین نتیجه ، در توصیف ویژگی های نظریه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) در مورد اینکه مجموعه قوانین سراسری اتوماتای سلولی بعنوان مجموعه ای از درون دگرگونی های پیوسته از فضای تغییر است.
در سال 1969 ، پیشگام کامپیوتر آلمانی ، کنراد تسوزه ، کتاب خود را با عنوان فضای محاسبه (به انگلیسی: Calculating Space) منتشر نمود. او در این کتاب مطرح نموده است که قوانین فیزیکی جهان توسط طبیعت گسسته شده است، و کل جهان خروجی یک محاسبه قطعی در یک ماشین سلولی منفرد است. نظریه تسوزه ، بنیانی برای شاخه ای علوم با نام فیزیک دیجیتال قرار گرفت.
در دهه 70 میلادی ، یک اتوماتای سلولی دو حالته ی دوبعدی با نام بازی زندگی (به انگلیسی: Game of Life) بصورت گسترده ای شناخته شد، بخصوص در انجمن های محاسباتی اولیه. این اوتوماتا توسط جان کانوی اختراع و توسط مارتین گاردنر در مقاله علمی آمریکایی به شهرت رسید. قوانین آن به صورت زیر است : اگر یک سلول دارای دو بلاک همسایه باشد ، به همان صورت قبل باقی می ماند. اگر سه بلاک همسایه داشته باشد ، سیاه می شود. در همه ی شرایط دیگر ، آن سلول سفید خواهدشد. بر خلاف سادگی آن ، سیستم به تنوع قابل توجهی در رفتار دست پیدا خواهد نمود ، که در حال نوسان به صورت رندوم ظاهری یا منظم هست. یکی از آشکاراترین ویژگی های بازی زندگی رخ دادن تکرار شونده ی گلایدرها (ترتیبی از سلول ها که بنا به ضرورت خودشان را در شبکه جابجا میکنند) است. این امکان پذیر است که به گونه ای اتوماتا را سازماندهی نماییم که گلایدرها به منظرو انجام محسابات با یکدیگر تعامل داشته باشند، و پس از تلاش های زیاد ، این نشان داده شد که بازی زندگی میتواند با یک تورینگ ماشین جهانی برابری نماید. این مساله به عنوان یک موضوع تفریحی تصور شده و کارهای بسیار کمی خارج از چارچوب بررسی خصوصیابازی زندگی و اندک قوانین مرتبط با آن در دهه 70 میلادی انجام پذیرفت.
استیون ولفرم به صورت مستقل کار بر روی اتوماتای سلولی را در اوسط سال 1981 ، پس از بررسی الگوهای پیچیده در طبیعت و نحوه شکل گیری آن ها بر خلاف قانون دوم ترمودینامیک ، آغاز نمود. تحقیقات او در ابتدا با تمرکز بر روی سیستم های مدلسازی مانند سیستم های عصبی اغاز شده بود. او اولین مقاله اش را در ژورنال Reviews of Modern Physics که تحقیق و بررسی بر روی اتوماتای سلولی پایه (به طور خاص اتوماتای 30 قانونه) بود ، در سال 1983 منتشر نمود. پیچیدگی غیر قابل انتظار در رفتار چینین قانون هایی ، ولفرم را به این جهت سوق داد که به این موضوع شک کند که پیچیدگی موجود در طبیعت نیز ناشی از مکانیزم مشابه ای باشد. با این وجود ، تحقیقات او موجب شد ، او دریابد که اتوماتای سلولی سیستم مدلسازی ضعیفی به منظور مدلسازی سیستم های عصبی محسوب می شود. علاوه بر این ، در طی این همین زمان ، ولفرم مفاهیم ذاتا تصادفی بودن و تقلیل ناپذیری را فرموله بندی نموده و پیشنهاد داد که اتوماتای 110 قانونه ممکن است همگانی باشد - این حقیقت بعدا توسط متیو کوک، دستیار تحقیقاتی ولفرم ، در سال 1990 اثبات گردید.
در سال 2002 ، ولفرم یک مستند 1280 صفحه ای با نام جنبه جدید از علوم (به انگلیسی: A New Kind of Science) منتشر نمود. در این متن ، ولفرم در مورد اینکه اکتشافات انجام شده در زمینه اتوماتای سلولی حقایق مجزا و منحصر به فردی نیستند ولی قدرتمند بوده و برای همه ی رشته های علمی پراهمیت هستند ، استدلال های گسترده ای را مطرح نمود. علی رغم سردرگمی زیاد مطبوعات ، این کتاب در مورد نظریه اساسی فیزیک مبتنی بر اتوماتای سلولی استدلالی مطرح نمی نماید. هر چند این کتاب تعداد کمی از مدل های خاص فیزیکی مبتنی بر اتوماتای سلولی را توصیف می نماید و همچنین مدل هایی مبتنی بر سیستم های انتزاعی با کیفیت های متفاوت ، ارایه می نماید.
طبقه بندی
ولفرم ، در کتاب جنبه جدید از علوم و مقالات بسیاری در سال های مربوط به اواسط دهه 80 میلادی ، چهار کلاس را در زمینه چگونگی تقسیم بندی اتوماتای سلولی و بسیاری از مدل های ساده محاسباتی دیگر بر اساس رفتارشان ، توصیف نمود . در حالی که مطالعات قبلی در زمینه اتوماتای سلولی ، به منظور تعیین نمودن انواع الگوها برای هر قانون مشخص بود ، طبقه بندی مطرح شده توسط ولفرم ، اولین تلاش در زمینه طبقه بندی خود قوانین بود. به ترتیب پیچیدگی ، این کلاس های بدین شرح می باشند :
کلاس اول : تقریبا تمام الگوهای پایه که به سرعت به یک حالت همگن و با ثبات توسعه می یابند. هیچ گونه تصادفی بودنی در الگوی پایه در نظر گرفته نخواهد شد.
کلاس دوم : تقریبا تمام الگوهای پایه که به سرعت به یک ساختار با ثبات و یا نوسانی توسعه می یابند. برخی از موارد تصادفی ، در این الگوی پایه در نظر گرفته نمی شود اما برخی از آن ها نیز لحاظ می گردد. تغییرات محلی بر روی الگوی پایه ، تمایل دارند به صورت محلی باقی بمانند.
کلاس سوم : تقریبا تمام الگوهای اولیه که به صورت شبه تصادفی و بی نظم توسعه می یابند. هرگونه ساختار با ثباتی که ظاهر شوند به سرعت توسط نویزهای اطراف از بین خواهند رفت. تغییرات محلی در الگوی پایه تمایل دارند به صورت نامحدودی منتشر شوند .
کلاس چهارم : تقریبا تمام الگوهای اولیه که به ساختارهایی با روش های پیچیده و جالب تعامل و با شکل گیری ساختار های محلی که قادر به زنده ماندن برای مدت طولانی هستند ، توسعه پیدا میکنند. کلاس نوع دوم ، ساختار های با ثبات و یا نوسانی ، ممکن است در نهایت به نتیجه برسند ، اما تعداد گام های مورد نیاز برای رسیدن به این حالت ، ممکن است بسیار زیاد باشد ، حتی اگر الگوی پایه نسبتا ساده باشد.تغییرات محلی بر روی الگوی پایه ممکن است به صورت نامحدودی منتشر گردد. ولفرم تخمین زده است که اگر نگوییم همه ، بسیاری از اتوماتا های سلولی کلاس 4 ، قادر به انجام محاسبات جهانی می باشند. این مساله برای 110 قانون و بازی زندگی مطرح شده توسط کانوی ، اثبات گردیده است.
این تعاریف در طبیعت به صورت کیفی بوده و فضاهایی به منظور تفسیر آن وجود دارد. بر اساس نظریه ولفرم ، "...با تقریبا هر الگوی طبق بندی عمومی ، موارد اجتناب ناپذیری وجود دارند که به یک کلاس با یک تعریف و به کلاس دیگر با تعریف دیگری اختصاص داده می شوند. بنابراین این مساله در اتوماتای سلولی وجود دارد که : قانون های وابسته موقعیتی وجود دارند که برخی ویژگی های یک کلاس و برخی ویژگی های کلاس دیگری را نمایش میدهند. طبقه بندی مطرح شده توسط ولفرم ، به صورت تجربی با یک خوشه بندی از خروجی طول فشرده اتوماتای سلولی منطبق است.
با الهام از طبقه بندی مطرح شده توسط ولفرم تلاش های متعددی به منظور طبقه بندی اوتاماتای سلولی در کلاس های فرمال دقیق وجود داشته است. به عنوان نمونه ، کولیک و یو سه کلاس خوش تعریف (و یک کلاس چهارمی برای اتوماتا که با هیچ کدام از این ها منطبق نیست) را مطرح نمودند. این کلاس ها برخی اوقات با نام کلاس های کولیک-یو نام برده می شوند. به اثبات رسیده است که عضویت در این کلاس ها تصمیم ناپذیر است. کلاس 2 طبقه بندی ولفرم را میتوان به دو زیر گروه قانون های با ثبات (ثابت) و نوسانی (پریودیک) تقسیم بندی نمود.
برگشت پذیر
یک اتوماتای سلولی معکوس پذیر است اگر برای هر پیکربندی جاری اتوماتای سلولی ، دقیقا یک پیکربندی قبلی (پیش تصویر) وجود داشته باشد. اگر یک تفکر در مورد اتوماتای سلولی این باشد که یک تابع به منظور نگاشت پیکربندی به پیکربندی است ، به صورت معکوس پذیر نشان میدهد که این تابع یک به یک است. اگر یک اتوماتای سلولی معکوس پذیر باشد ، رفتار زمان معکوس آن نیز میتواند به عنوان یک اتوماتای سلولی توصیف گردد. این حقیقت از نتایج قضیه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) که در رابطه با ویژگیهای توپولوژیکال اتوماتای سلولی است، می باشد. برای اتوماتای سلولی که در آن هر پیکربندی یک پیش تصویر ندارد ، پیکربندی های بدون پیش تصویر الگوهای پیوسته و متراکم ادن (به انگلیسی: Garden of Eden) نامیده می شوند.
برای اتوماتای تک بعدی ، الگوریتم های شناخته شده ای به منظور تشخیص معکوس پذیری با معکوس ناپذیری یک قانون وجود دارد. با این حال ، برای اتوماتای های دو بعدی یا چند بعدی معکوس پذیری تصمیم ناپذیر است ، بدین معنا که ، الگوریتم یوجود ندارد که به عنوان ورودی یک قانون اتوماتا دریافت نموده و تضمین کند که میتواند به صورت درستی معکوس پذیری آن را تعیین نماید. اثبات مطرح شده توسط جارکو کری به مشکل کاش کاری موجود در مدل ونگ تایلز مرتبط است.
اتوماتای سلولی معکوس پذیر ، اغلب به منظور شبیه سازی پدیده های فیزیکی مانند مباحث حرکتی گاز و مایع مورد استفاده قرار میگیرد. زیرا آن ها از قوانین ترمودینامیک پیروی میکنند. چنین اتوماتای سلولی قانون هایی دارد که به صورت ویژه به گونه ای ساخته شده اند که معکوس پذیر باشد.چنین سیستم هایی توسط نرمن مارگولس و توماس توفولی و دیگران مورد مطالعه قرار گرفته است. تکنیک های متعددی می تواند به منظور ساخت صریح اتوماتای سلولی معکوس پذیر با معکوس های شناخته شده ، مورد استفاده قرار بگیرد. دو نوع متداول از این تکنیک ها ،اتوماتای سلولی مرتبه دوم (به انگلیسی: second order cellular automaton) و اتوماتای سلولی بلاکی (به انگلیسی: block cellular automaton) می باشند. هر دو اینها بیانگر تعریف هایی از طرق مختلف برای یک اتوماتای سلولی هستند. هرچند چنین اتوماتایی تعریف بیان شده در بالا را کاملا بر آورده نمی کند ، میتواند نشان دهد که آنها میتوانند با اتوماتای سلولی متعارف با تعداد همسایگی و تعداد حالت های به اندازه کافی بزرگ شبیه سازی شوند ، و بنابراین میتواند بعنوان زیرمجموعه ای از اتوماتای سلولی متعارف مطرح گردد. بطور عکس ، میتواند نشان داده شود که هر اتوماتای سلولی معکوس پذیری میتواند با یک اتوماتای سلولی بلاکی شبیه سازی شود.
تک گرایی
یک کلاس خاص از اتوماتای سلولی ، اتوماتای سلولی تک گرایی (به انگلیسی: Totalistic) است . حالت هر سلول در اتوماتای سلولی تک گرا به وسیله یک عدد نشان داده می شود. (معمولا یک عدد صحیح گرفته شده از یک مجموعه متناهی) ، و مقدار یک سلول در زمان t فقط به مجموع مقادیر سلول های موجود در همسایگی آن در زمان t-1 بستگی دارد. (احتمالا از جمله خود آن سلول). اگر حالت سلول در زمان t به مقدار خودش در زمان t-1 وابسته باشد ، این اتوماتای سلولی ، تک گرای خارجی نامیده میشود. بازی زندگی مطرح شده توسط کانوی یک نمونه از اتوماتای فوق با مقادیر 0 و 1 برای سلول ها است. اتوماتای سلولی تک گرای خارجی با ساختار همسایگی از نوع مور ، مشابه با زندگی برخی اوقات اتوماتای سلولی زندگی مانند نامیده می شود.
اتوماتای مرتبط
تعمیم های زیادی برای مفهوم اتوماتای سلولی امکان پذیر است. یک راه استفاده از چیز دیگری به جای شبکه چهارخانه است. (مکعبی و غیره) بعنوان مثال ، وقتی طرح کاشی با شش ضلعی های منظم است ، این شش گوشه ها می توانند به عنوان سلول مورد استفاده قرار بگیرند. در بسیاری از موارد ، اتوماتای سلولی حاصل شده ، با اتوماتا هایی با شبکه چهار خانه با طراحی خاص همسایگی و قانون ها ، برابری میکند. نوع دیگر می تواند پیاده سازی نامنظم خود شبکه باشد ، به عنوان مثال مدل پنروس تایل (به انگلیسی: Penrose tiling) .
یک اتوماتای سلولی مبتنی بر سلول های شش گوش. (قانون 34/2)
همچنین ، قانون ها نیز میتوانند احتمالی باشد به جای آنکه قطعی باشند. چنین اتوماتای سلولی ، اتوماتای سلولی احتمالی نامیده می شوند. قانون های احتمالی ، به هر الگو در زمان t ، احتمالاتی به منظور گذر از سلول مرکزی به هر حالت ممکن در زمان t+1 اختصاص میدهند. برخی اوقات ، یک قانون ساده تر مورد استفاده قرار میگیرد. بعنوان مثال : "بازی زندگی یک قانون است ، اما برای هر گام زمانی احتمال 0.001% وجود دارد که هر سلول به رنگ مخالف خود گذر داشته باشد".
همسایگی و یا قانون ها میتوانند در طول زمان یا مکان تغییر کنند. به عنوان مثال ، در ایتدا ، حالت جدید یک سلول می تواند توسط سلول های افقی مجاور تعیین گردد ، اما برای توسعه بعدی می تواند سلول های عمودی مورد استفاده قرار بگیرد.
در اتوماتای سلولی ، حالت جدید سلول ،تحت تاثیر حالت جدید سلول های دیگر نمی باشد. این موضوع می تواند تغییر کند ، به گونه ای که ، بعنوان نمونه ، یک بلاک دو در دو از سلول ها می تواند توسط خود آن سلول و سول های مجاورش تعیین گردد.
اتوماتاهای پیوسته نیز وجود دارد . این ها شبیه اتوماتای سلولی تک گرا هستند ، اما بجای اینکه قانون ها و حالت ها بصورت گسسته(به عنوان مثال ، یک جدول که از حالت های {0,1,2}) باشند ، توابع پیوسته مورد استفاده قرار میگیرد ، و حالت ها بصورت پیوسته می شوند. (معمولا مقادیری در بازه 0,1) و حالت های مکان ، یک تعداد متناهی از اعداد حقیقی می باشد. اتوماتاهای سلولی خاصی میتوانند بر اساس الگوهای شناور مانند این عمل نمایند.
اتوماتای فضایی پیوسته ، یک رشته پیوسته از مکان ها دارد. حالت یک مکان یک تعداد متناهی از یک مجموعه اعداد حقیقی است. زمان هم بصورت پوسته بوده و حالت با توجه به معادلات دیفرانسیل تکامل می یابد. یک نمونه مهم ، ساختارهای واکنش-انتشار می باشد ، معادلات دیفرانسیلی که توسط تورینگ به منظور توضیح نحوه ایجاد هاشور در خر ها و نحوه ایجاد نقاط در پلنگ توسط واکنش های شیمیایی معرفی شد. زمانی که اینها توسط اتوماتای سلولی تقریب زده شده ، آن ها اغلب بر اساس الگوهای مشابه ای عمل می کنند. مک لنان، اتوماتای فضایی پیوسته را به عنوان یک مدل محاسباتی در نظر میگیرد.
مثال های شناخته شده ای برای اتوماتای فضایی پیوسته وجود دارد که پدیده انتشار را مشابه گلایدر های در بازی زندگی نمایش می دهند.
ماشین های سلولی ابتدایی
ساده ترین اتوماتای سلولی مهم می تواند یک بعدی ، با دو حالت امکان پذیر برای هر سلول ، که همسایه ها ، سلول های مجاور در دو طرف آن تعریف می شود ، می باشد. یک سلول و دو همسایه آن ، همسایگی از سه سلول را می سازند. بنابراین 8 الگوی ممکن برای همسایگی وجود دارد. یک قانون شامل تصمیم گیری برای هر الگوست که تعیین میکند در توسعه بعدی سلول باید 0 باشد یا 1.
بر این اساس 256 قانون امکان پذیر وجود دارد. این 256 اتوماتای سلولی به طور کلی بر اساس کد ولفرم آنها (یک قرداد نامگذاری استاندارد که توسط ولفرم مطرح شد. این استاندارد به هر قانون یک عدد از 0 تا 255 تخصیص میدهد ) ارجاع داده می شوند. تعدادی از مقالات به تحلیل و مقایسه این 256 اتوماتای سلولی پرداخته اند. اتوماتای سلولی قانون 30 و 110 رولی به طور خاص ، جالب هستند. تصویر زیر ، سابقه هر کدام را زمانی که پیکر بندی آغازین شامل یک 1 (در قسمت بالای هر تصویر ) که توسط 0 ها احاطه شده است ، نشان می دهد. هر ردیف از پیکس ها ، یک توسعه را در سابقه اتوماتا نشان می دهد ، t=0 بالاترین ردیف می باشد. هر پیکسل 0 با رنگ سفید و هر پیکسل 1 با رنگ سیاه ، رنگ آمیزی شده است.
اتوماتای سلولی 30 قانونی
اتوماتای سلولی 110 قانونی
مدل 30 قانونه رفتار کلاس 3 را نمایش می دهد. بدین معنا که الگوهای ساده مشابه آنچه نشان داده شده ، منجر به ایجاد سوابقی بی نظرم و ظاهرا تصادفی می گردند. مدل 110 قانونه، مشابه بازی زندگی، چگونگی رفتار چیزی که ولفرم آن را کلاس 4 نامیده است را نشان می دهد که رفتاری نه کاملا تصادفی و نه کاملا تکراری دارند. ساختارهای محلی ظاهر می شوند و از راه های جستجوی پیچیده مختلف با یکدیگر تعامل میکنند. در طی توسعه کتاب جنبه جدید از علوم ، همانطوری که دستیار تحقیقاتی ولفرم در سال 1994 ، متیو کوک اثبات نموده بود که برخی از این ساختار ها به اندازه کافی قوی هستند که بتواند جامعیت (عمومیت) را پشتیبانی کنند. این نتیجه جالب است زیرا 110 قانونه یک سیستم تک بعدی کاملا ساده و سیستمی است که برای یک مهندس انجام چینین رفتار خاصی مشکل است.
بنابراین این نتیجه حمایت قابل توجهی را برای دیدگاه ولفرم که سیستم های کلاس 4 ، به نظر میرسد به طور ذاتی یک سیستم جهانی باشند ، فراهم آورد. کوک اثبات خود را در یک کنفرانس اتوماتای سلولی مؤسسه سنتا فه در سال 1998 مطرح نمود اما ولفرم مانع از قرارگیری این اثبات در مجموعه مقالات کنفرانس گردید. زیرا ولفرم نمیخواست که پیش از انتشار کتاب جنبه جدید از علوم این اثبات انتشار پیدا کند. در سال 2004 ، اثبات کوک سرانجام در ژورنال ولفرم (سری 15 ، شماره 1) منتشر شد، ده سال پس از زمانی که کوک آن را مطرح نموده بود. 110 قانونه شامل پایه هایی می شود که برخی از کوچکترین ماشین های تورینگ جهانی بر اساس آن ساخته شده اند.
فضای قانون
قانون ابتدایی اتوماتای سلولی ، توسط 8 بیت مشخص شده است ، و همه قانون های ابتدایی اتوماتای سلولی میتوانند بر روی روئوس یک واحد ابر مکعب هشت بعدی در نظر گرفته شوند. این واحد ابر مکعب فضای قانون اتوماتای سلولی می باشد. برای نزدیکترین همسایه بعدی اتوماتای سلولی ، یک قانون با 32 بیت مشخص می گردد، و فضای قانون اتوماتای سلولی یک واحد ابرمکعب 32 بعدی می باشد. فاصله میان دو قانون ، می تواند به وسیله تعداد گام های مورد نیاز برای حرکت از یک راس ، که قانون اول را مشخص می کند ، به راس دیگر ، که قانون دیگر را مشخص می کند ، در امتداد لبه ابر کعب ، مشخص شود. این فاصله قانون تا قانون همچنین فاصله همینگ نیز نامیده می شود.
فضای قانون اتوماتای سلولی به ما اجازه می دهد که بپرسیم آیا قانون هایی با رفتار پویای مشابه در نزدیکی هم قرار دارند یا خیر. از نظر گرافیکی ، ترسیم یک ابر مکعب با تعداد بعد زیاد ، در یک صفحه دو بعدی یک کار دشوار باقی مانده است ، و یک مکان یاب خام یک قانون در ابرمکعب ، بیت شماره 1 در میان رشته 8 بیتی مربوط به قانون مقدماتی (و یا رشته 32 بیتی برای قانون های نزدیکترین همسایه بعدی ) می باشد. ترسیم قانون ها در کلاس مختلف مدل ولفرم در این چنین برش هایی از فضای قانون ، نشان می دهد که قانون های کلاس 1 ، متمایل به داشتن تعداد کمتری از بیت 1 هستند ، در نتیجه در یک ناحیه از فضا قرار دارند. در حالی که قانون های کلاس 3 ، تمایل به داشتن تعداد بیت 1 با نسبتی بیشتر از 50 درصد دارند.
برای فضای قانون های بزرگتر اتوماتای سلولی ، نشان داده شده است که قانون های کلاس 4 ، در موقعیتی بین کلاس 1 و 3 قرار گرفته اند. این مشاهدات پایه و اساس اصطلاح کناره های بی نظمی و یاد آور انتقال فاز در ترمودینامیک می باشد.
زیست شناسی
یک الگوی اتوماتای سلولی را در سطح خود نمایش می دهد.
برخی از فرآیندهای زیستی بر اساس اتوماتای سلولی اتفاق افتاده و یا میتوانند شبیه سازی شوند. الگوی برخی از صدف ها ، شبیه صدف های نوع کانوس و سیمبیولا ، توسط اتوماتای سلولی طبیعی تولید شده اند. سلول های رنگدانه ای در یک نوار باریک در لبه پوسته آن ها قرار دارند. هر سلول با پیروی از یک نسخه طبیعی از قوانین ریاضی، با توجه به فعال یا غیر فعال بودن سلول های رنگدانه ای همسایه اش ، رنگدانه ترشح می کند. نوار سلول الگوی رنگی را همانطوری که پوسته یه ارامی در حال رشد است، بر روی آن قرار می دهد. به عنوان مثال ، گونه گسترده تر کانوس، یک الگوی مشابه با اتوماتای 30 قانونه مدل ولفرم را در بر دارد.
گیاهان مصرف و از دست دادن گازها (بخارها) را از طریق یک مکانیزم ماشین سلولی تنظیم می نمایند. هر روزنه در برگ به عنوان یک سلول عمل می کند.
الگوهای امواج متحرک بر روی سطح سفالوپودها را می توان با یک اتوماتای سلولی دو بعدی دو حالته شبیه سازی نمود. هر حالت بر اساس یک کراماتوفر توسعه یافته و یا لغو شده است.
اتوماتای آستانه ای به منظور شبیه سازی نورون ها ایجاد گردید و با به کارگیری آن رفتارهای پیچیده مانند شناخت و یادگیری قابل شبیه سازی می باشد.
فیبروبلاست ها شباهت هایی با اتوماتای سلولی دارند، بدین صورت که هر فیبروبلاست فقط با هماسیگان خود تعامل دارد.
انواع شیمیایی
واکنش بلوسوف-ژابوتینسکی یک اوسيلاتور شیمیایی فضا-زمانی است که می تواند با روش های اتوماتای سلولی شبیه سازی شود. در دهه 50 میلادی ، ژابوتینسکی ، (کار بلوسوف را گسترش داد) کشف کرد که هنگامی که یک لایه همگن نازک از مخلوطی از مالونیک اسید ، برمات اسیدی و نمک سریک با هم مخلوط شده و در سکون قرار داده می شوند ، طرح های هندسی جذاب مانند دایره متحد المرکز و مارپیچی در سراسر آن منتشر می شوند. الکساندر ددنی ، در بخش "Computer Recreations" از شماره آگوست سال 1988 مجله ساینتیفیک آمریکن ، یک ماشین سلولی که توسط که توسط مارتین گرهارد و هایک شوستر از دانشگاه بیلفد (آلمان غربی) توسعه داده شد مورد بحث قرار داد. این اتوماتا الگوهای موجی شبیه آنچیزی که در واکنش بلوسوف-ژابوتینسکی است ، تولید می نماید.
کاربرد ها
پردازنده های کامپیوتر
پردازنده های اتوماتای سلولی پیاده سازی فیزیکی مفاهیم CA هستند ، که میتواند اطلاعات را از بعد محاسباتی پردازش نماید. مولفه های پردازش ها در یک شبکه منظم از سلول های یکسان سازماندهی شده اند. این شبکه معمولا یک کاشی کاری مربعی، و یا موزاییک کاری، از دو یا سه بعد می باشد. سایر انواع کاشی کاری نیز امکان پذیر است ولی هنوز مورد استفاده قرار نگرفته است. حالت های سلول فقط به وسیله تعامل آن با همسایگان مجاورش مشخص می شود. هیچ راهی برای برقراری ارتباط مستقیم با سلول های دورتر وجود ندارد. یکی از نمونه های چنین پردازنده اتوماتای سلولی پیکربندی آرایه ، آرایه های سیستولیک می باشد. تعاملات سلولی می تواند از طریق بار الکتریکی ، مغناطیس ؛ ارتعاشات (فونون در مقیاس کوانتومی) و یا هر روش فیزیکی دیگری انجام پذیرد. این مساله می تواند از طرق مختلفی انجام گیرد بنابراین هیچ اتصال سیمی میان مولفه ها نیاز نیست. این پردازنده با پردازنده هایی که امروزه در بیشتر کامپیوتر ها مورد استفاده قرار میگیرند (طراحی ون نیومن) کاملا متفاوت است. در طراحی ون نیومن ، پردازنده به بخش ها به همراه مولفه هایی تقسیم شده است که می توانند با مولفه های راه دور از طریق سیم ها ، ارتباط برقرار نمایند.
رمز نویسی
مدل ۳۰ قانونه در اصل بعنوان یک رمز گذار بلوکی امکان پذیر برای استفاده در رمزگذاری قطعه‌ای پیشنهاد گردید. اتوماتای سلولی دو بعدی برای تولید عدد تصادفی مورد استفاده قرار گرفته است. اتوماتای سلولی برای رمزنگاری کلید عمومی ارائه شده است . تابع یک طرفه ، تکامل یک CA متناهی است که یافتن معکوس آن به نظر دشوار میرسد. با توجه به قانون، هر کسی می تواند به راحتی حالت های آینده را محاسبه نماید، اما به نظر می رسد که محاسبه حالت های قبلی بسیار دشوار باشد.
کد های تصحیح خطا
مدل اتوماتای سلولی (به انگلیسی: CA) به منظور طراحی کدهای تصحیح خطا در مقاله "Design of CAECC – Cellular Automata Based Error Correcting Code" مورد استفاده قرار گرفته است. این مقاله یک طرح جدید از ساختن کدهای همینگ SEC-DED با استفاده از CA را توصیف نموده است. و همچنین گزارشی از یک رمزگشای سخت افزاری سریع نیز در این مقاله آمده است.
مدل سازی واقعیت های فیزیکی
همانگونه که آندر ایلاچینسکی در اتوماتای سلولی خود اشاره نمود، بسیاری از محققین این سوال را مطرح نموده اند که آیا جهان یک اتوماتای سلولی است.او استدلال می کند که اهمیت این سوال ممکن است با یک مشاهده ساده ، بهتر مشخص گردد، این مشاهده می تواند به شرح زیر بیان گردد.
سیر تکاملی 10 قانونه را در نظر بگیرید : اگر این قانون یک نوع فیزیک خارج از بعد باشد، توصیف مناسب الگوهای مشاهده شده چه خواهد بود؟ اگر یک ناظر نداند که چگونه تصاویر تولید شده است، او ممکن است در نهایت بتواند حدس هایی در مورد حرکت برخی اشیای ذره مانند بیان نماید. یک فیزیکدان به نام جیمز کراچفیلد بر مبنای این ایده یک تئوری ریاضی دقیق مطرح نمود که پیدایش آماری از ذرات ، از اتوماتای سلولی را اثبات می کند. در آن زمان ، همانگونه که این استدلال به پیش می رود ، مساله تعجب آور می تواند این باشد که جهان که در حال حاضر به وسیله فیزیک و با اشیای ذره مانند (فیزیک ذرات) توصیف می شود، می تواند یک اتوماتای سلولی در پایه ای ترین سطح آن باشد. در حالی که تئوری کامل در این زمنیه همچنان در حال توسعه است ؛ توسعه این فرضیه ، محققان را بر آن داشت که حدس و گمان های جالب و شهود های مثمر ثمری را در زمینه چگونگی قابل درک بودن جهان در یک چارچوب گسسته مطرح نمایند. ماروین مینسکی یکی از پیشگامان هوش مصنوعی ، به بررسی چگونگی درک نحوه تعامل ذرات با شبکه اتوماتای سلولی چهار بعدی پرداخت ؛ کنراد تسوزه مخترع اولین کامپیوتر ، Z3 ، یک شبکه منظم به منظور بررسی پرسشی مبنی بر محتوای اطلاعاتی ذرات ، مطرح نمود.اخیرا ادوارد فردکین ، چیزی را که خودش "فرضیه طبیعت محدود" می نامد را به نمایش گذاشت. به عنوان مثال، این ایده که در نهایت هر کمیت فیزیکی، از جمله فضا و زمان، به کیمیت هایی گسسته و محدود تبدیل خواهد شد. فردکین و ولفرم از طرفداران سر سخت فیزیک مبتنی بر اتوماتای سلولی هستند.
در سال های اخیر ، پیشنهادهای دیگری در این زمینه ، در میان مقالات مرتبط با محاسبات غیر استاندارد مطرح گردید. کتاب جنبه دیگری از علوم ، اتوماتای سلولی را به عنوان کلیدی برای درک مسایل مختلف شامل فیریک ، در نظر گرفته است. ریاضیات مدلی بر اساس منابع (به انگلیسی: Mathematics of the Models of Reference)، یک جهان اصلی دو بعدی /سه بعدی مبتنی بر یک شبکه "لوزی دوازده وجهی" جدید و یک قانون منحصر به فرد را نشان داد. این مدل عمومیت (جامعیت) را تامین نموده (این مدل با ماشین تورینگ برابری می کند)، معکوس پذیری را کامل نموده (یک ضرورت که اگر کسی خواست بتواند کمیت های متعددی را ذخیره کند و اطلاعات از بین نرود) و در نظریه مرتبه اول گنجانده شده است که اجازه محاسبه عبارات کیفی در مورد تکامل جهان را داده است.
چکیده
یک چنبره، یک شکل چنبره ای
یک راه برای شبیه سازی اتوماتای سلولی دو بعدی ، استفاده از تعداد متناهی صفحات کاغذ میلیمتری به همراه مجموعه از قوانین برای سلول ها می باشد. هر مربع یک "سلول" نامیده می شود و برای هر سلول دو حالت امکان پذیر است ، سیاه و سفید. همسایه های سلول نزدیکترین و معمولا سلول های مجاور آن هستند. دو نوع از رایج ترین انواع همسایه ها ، همسایه های ون نیومن و همسایه های مور هستند. مدل اول ، پس از مطرح شدن نظریه پرداز اتوماتای سلولی ، شامل چهار سلول تعامد (جبر خطی) ، نامگذاری شد. مدل دوم شامل همسایه نوع ون نیومن هست و علاوه بر آن چهار سلول باقی مانده در اطراف سلولی که باید حالتش محاسبه شود را نیز شامل می گردد. برای یک چنین سلولی و همسایه نوع مور آن ، 512 الگوی امکان پذیر وجود دارد. برای هر یک از 512 الگوی امکان پذیر ، جدول قوانین مشخص خواهد کرد که حالت سلول مرکزی در فاصله زمانی بعدی سیاه یا سفید خواهد بود. بازی زندگی کانوی یک نسخه محبوب و عمومی از این مدل است. یک مدل رایج دیگر از انواع همسایه ، همسایه مدل ون نیومن بسط یافته است که شامل دو نزدیک ترین سلول در هر جهت متعامد ، برای کل هشت خانه ، می باشد. معادله عمومی برای چنین سیستمی از قوانین ، k به قوه k به قوه s می باشد که K در آن تعداد حالت های ممکن برای یک سلول و S تعداد سلول های همسایه (از جمله خود سلولی مورد نظر) که به منظور تعیین حالت بعدی سلول مورد استفاده قرار میگیرد. بنابراین در یک سیستم دوبعدی با همسایه از نوع مور ، تعداد کل اتوماتای ممکن برابر است با229, یا۱.۳۴×۱۰۱۵۴. اغلب فرض می شود همه سلول ها در جهان از یک حالت یکسان شروع می شوند ، به جز برای تعداد متناهی سلول در حالت های دیگر ؛ فرآیند تخصیص مقادیر به حالت ها پیکربندی نامیده می شود. به طور کلی ، گاهی اوقات فرض می شود جهان در آغاز با یک الگوی تناوبی پوشش داده شده است و فقط تعداد متناهی از سلول ها از این الگو پیروی نمیکند. فرض دوم در اتوماتای سلولی یک بعدی رایج است.
اتوماتای سلولی اغلب بر روی شبکه متناهی شبیه سازی می شود تا یک شبکه نامتناهی. در حالت دو بعدی ، جهان باید بصورت چهارگوش باشد بجای یک صفحه نامتناهی. مشکل مشاهده شده در مورد شبکه های محدود این است که چگونه سلول ها را در گوشه ها مدیریت نماییم. نحوه مدیریت آن ها بر روی مقادیر همه ی سلول ها در شبکه تاثیر گزار خواهد بود. یکی متد امکان پذیر این است که اجازه دهیم مقادیر در این سلول ها ثابت باقی بمانند. یک متد دیگر می تواند این باشد که همسایه را برای اینگونه سلول ها به گونه ای متفاوت تعریف نماییم. ممکن است یک نفر بیان کند که این سلول ها همسایه های کمتری دارند ، اما در این صورت مجبور به تعریف قوانین جدیدی برای سلول های موجود در گوشه ها خواهیم بود. این سلول ها معمولا با یک ترتیب toroidal مدیریت می شوند. این میتواند بدین صورت تصویر سازی شود که گوشه ها چپ و راست چهارگوش را به یکدیگر متصل نموده و یک تویوپ ایجاد نماییم ، سپس بالا و پایین گوشه های تیوپ را به یکدیگر متصل نموده و یک چنبره (شکلی همانند حلقه) ایجاد نماییم. فضاهای مربوط به سایر ابعاد به شیوه ای مشابه مدیرت می شوند. این کار به منظور حل مشکل حدود مرزی در همسایگی ها انجام شده است ، اما یک مزیت دیگر این سیستم این است که به راحتی توسط توابع هم‌نهشتی (نظریه اعداد) قابل برنامه ریزی است. به عنوان مثال ، در یک اتوماتای سلولی تک بعدی ، مانند مثال زیر ، همسایگی سلول xit برابر است با {xi−1t−1, xit−1, xi+1t−1} ، که t گام های زمانی (قایم) ، و i ایندکس (افقی) در یک گسترش می باشد.
تاریخچه
جان فون نویمان، نشان شناسایی در آزمایشگاه ملی لس آلاموس
استنی‌سواف اولام ، زمانی که در آزمایشگاه ملی لس آلاموس ، در دهه 40 میلادی مشغول به کار بود ، بر روی رشد کریستال ها با به کارگیری یک مدل شبکه توری منظم به عنوان مدل خود، مطالعه مینمود. در همان زمان ، جان فون نویمان ، همکار اولام در لس آلاموس ، بر روی مشکلات سیستم های خود تکرار یا همان خودجایگزین‌گری کار میکرد. طراحی اولیه ون نیومن بر اساس ساخته شدن یک ربات توسط یک ربات دیگر بنا نهاده شد. این طراحی به عنوان مدل حرکتی شناخته می شود. در روند توسعه این طراحی ، ون نیمن متوجه مشکل بزرگی در زمینه ساخت یک روبات خود تکرار شد ، و هزینه بالای در تولید ربات به همراه دریایی از قطعات که برای ساخت تکرارش نیاز دارد نیز از دیگر مشکلات است. نیومن یک مقاله با عنوان "نظریه منطقی و عمومی اتوماتا" در سال 1948 در نشست هیگزون مطالعه کرد. اولام کسی بود که پیشنهاد استفاده از یک سیستم گسسته برای ایجاد یک مدل کاهش یافته از مدل خود تکرار را مطرح نمود. نیلز آل باریچرلی بسیاری از کشفیات اولیه در زمینه این مدل های زندگی مصنوعی را انجام داده است.
اولام و ون نیومن یک متد به منظور محسابه حرکت مایع در اوخر دهه 50 میلادی ایجاد نمودند. مفهوم موثر این متد در نظر گرفتن مایع به عنوان گروهی از واحد های گسسته و محاسبه حرکت هر کدام بر اساس رفتار همسایگان خود بوده است. بدین سان اولین سیستم اتوماتای سلولی متولد شد. همانند شبکه توری منظم اولام ، اتوماتای سلولی طراحی شده توسط ون نیومن بصورت دو بعدی با الگوریتم خود تکرار او پیاده سازی شده است. نتیجه یک سازنده کپی کننده جهانی که با یک اتوماتای سلولی و مجموعه کوچکی از همسایگان.(فقط این سلول هایی که با آن ها در تماس هستند به عنوان همسایه محسوب می شوند ، برای اتوماتای سلولی مدل ون نیون ، فقط سلول های متعامد ) و 29 حالت برای هر سلول ، بود. ون نیومن یک نظریه اثبات وجود مطرح نمود که یک الگوی مشخص ، یک کپی بی پایان از خود را درون جهان سلولی داده شده به وسیله طراحی پیکره بندی 200000 سلول که بتوانند چنین کاری انجام دهند ، ایجاد خواهد نمود. این طراحی با عنوان مدل موزائیک‌کاری (به انگلیسی: Tessellation) شناخته شده است و با نام سازنده جهانی ون نیومن نامیده میشود.
همچنین در دهه 40 میلادی ، نوربرت وینر و آرتور رونزبلاس یک مدل از رسانه های تحریک پذیر را با به کارگیری برخی ویژگی های یک اتوماتای سلولی توسعه دادند. انگیزه اصلی آن ها ، توصیف ریاضی انتقال ضربه در سیستم های قلبی بود. با این وجود مدل آن ها یک اتوماتای سلولی نیست زیرا حداقل ، انتشار سیگنال در آن پیوسته و جبهه های موج بصورت منحنی است. یک مدل اتاماتای سلولی صحیح از رسانه تحریک پذیر توسط گرینبرگ و هستینگ در سال 1978 توسعه یافته و مورد مطالعه قرار گرفت. کار اصلی وینر و رونزبلاس شامل نگرش های مختلفی است و همچنان در نشریان مدرن تحقیقاتی در زمینه بی نظمی قلبی و سیستم های تحریک پذیر مطرح می باشد.
در دهه 60 میلادی اتوماتای سلولی به عنوان بخش مشخصی از سیستم پویا مورد مطاله قرار گرفت و اتصال آن با مبحث ریاضیاتی از پویایی سمبلیک برای اولین بار محقق گردید. در سال 1969 ، هدلند نتایج زیادی را مبتنی بر همین دیدگاه گردآوری نمود. چیزی که هنوز هم به عنوان یک مقاله اصلی برای مطالعه ریاضیاتی اتوماتای سلولی در نظر گرفته می شود. اساسی ترین نتیجه ، در توصیف ویژگی های نظریه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) در مورد اینکه مجموعه قوانین سراسری اتوماتای سلولی بعنوان مجموعه ای از درون دگرگونی های پیوسته از فضای تغییر است.
در سال 1969 ، پیشگام کامپیوتر آلمانی ، کنراد تسوزه ، کتاب خود را با عنوان فضای محاسبه (به انگلیسی: Calculating Space) منتشر نمود. او در این کتاب مطرح نموده است که قوانین فیزیکی جهان توسط طبیعت گسسته شده است، و کل جهان خروجی یک محاسبه قطعی در یک ماشین سلولی منفرد است. نظریه تسوزه ، بنیانی برای شاخه ای علوم با نام فیزیک دیجیتال قرار گرفت.
در دهه 70 میلادی ، یک اتوماتای سلولی دو حالته ی دوبعدی با نام بازی زندگی (به انگلیسی: Game of Life) بصورت گسترده ای شناخته شد، بخصوص در انجمن های محاسباتی اولیه. این اوتوماتا توسط جان کانوی اختراع و توسط مارتین گاردنر در مقاله علمی آمریکایی به شهرت رسید. قوانین آن به صورت زیر است : اگر یک سلول دارای دو بلاک همسایه باشد ، به همان صورت قبل باقی می ماند. اگر سه بلاک همسایه داشته باشد ، سیاه می شود. در همه ی شرایط دیگر ، آن سلول سفید خواهدشد. بر خلاف سادگی آن ، سیستم به تنوع قابل توجهی در رفتار دست پیدا خواهد نمود ، که در حال نوسان به صورت رندوم ظاهری یا منظم هست. یکی از آشکاراترین ویژگی های بازی زندگی رخ دادن تکرار شونده ی گلایدرها (ترتیبی از سلول ها که بنا به ضرورت خودشان را در شبکه جابجا میکنند) است. این امکان پذیر است که به گونه ای اتوماتا را سازماندهی نماییم که گلایدرها به منظرو انجام محسابات با یکدیگر تعامل داشته باشند، و پس از تلاش های زیاد ، این نشان داده شد که بازی زندگی میتواند با یک تورینگ ماشین جهانی برابری نماید. این مساله به عنوان یک موضوع تفریحی تصور شده و کارهای بسیار کمی خارج از چارچوب بررسی خصوصیابازی زندگی و اندک قوانین مرتبط با آن در دهه 70 میلادی انجام پذیرفت.
استیون ولفرم به صورت مستقل کار بر روی اتوماتای سلولی را در اوسط سال 1981 ، پس از بررسی الگوهای پیچیده در طبیعت و نحوه شکل گیری آن ها بر خلاف قانون دوم ترمودینامیک ، آغاز نمود. تحقیقات او در ابتدا با تمرکز بر روی سیستم های مدلسازی مانند سیستم های عصبی اغاز شده بود. او اولین مقاله اش را در ژورنال Reviews of Modern Physics که تحقیق و بررسی بر روی اتوماتای سلولی پایه (به طور خاص اتوماتای 30 قانونه) بود ، در سال 1983 منتشر نمود. پیچیدگی غیر قابل انتظار در رفتار چینین قانون هایی ، ولفرم را به این جهت سوق داد که به این موضوع شک کند که پیچیدگی موجود در طبیعت نیز ناشی از مکانیزم مشابه ای باشد. با این وجود ، تحقیقات او موجب شد ، او دریابد که اتوماتای سلولی سیستم مدلسازی ضعیفی به منظور مدلسازی سیستم های عصبی محسوب می شود. علاوه بر این ، در طی این همین زمان ، ولفرم مفاهیم ذاتا تصادفی بودن و تقلیل ناپذیری را فرموله بندی نموده و پیشنهاد داد که اتوماتای 110 قانونه ممکن است همگانی باشد - این حقیقت بعدا توسط متیو کوک، دستیار تحقیقاتی ولفرم ، در سال 1990 اثبات گردید.
در سال 2002 ، ولفرم یک مستند 1280 صفحه ای با نام جنبه جدید از علوم (به انگلیسی: A New Kind of Science) منتشر نمود. در این متن ، ولفرم در مورد اینکه اکتشافات انجام شده در زمینه اتوماتای سلولی حقایق مجزا و منحصر به فردی نیستند ولی قدرتمند بوده و برای همه ی رشته های علمی پراهمیت هستند ، استدلال های گسترده ای را مطرح نمود. علی رغم سردرگمی زیاد مطبوعات ، این کتاب در مورد نظریه اساسی فیزیک مبتنی بر اتوماتای سلولی استدلالی مطرح نمی نماید. هر چند این کتاب تعداد کمی از مدل های خاص فیزیکی مبتنی بر اتوماتای سلولی را توصیف می نماید و همچنین مدل هایی مبتنی بر سیستم های انتزاعی با کیفیت های متفاوت ، ارایه می نماید.
طبقه بندی
ولفرم ، در کتاب جنبه جدید از علوم و مقالات بسیاری در سال های مربوط به اواسط دهه 80 میلادی ، چهار کلاس را در زمینه چگونگی تقسیم بندی اتوماتای سلولی و بسیاری از مدل های ساده محاسباتی دیگر بر اساس رفتارشان ، توصیف نمود . در حالی که مطالعات قبلی در زمینه اتوماتای سلولی ، به منظور تعیین نمودن انواع الگوها برای هر قانون مشخص بود ، طبقه بندی مطرح شده توسط ولفرم ، اولین تلاش در زمینه طبقه بندی خود قوانین بود. به ترتیب پیچیدگی ، این کلاس های بدین شرح می باشند :
کلاس اول : تقریبا تمام الگوهای پایه که به سرعت به یک حالت همگن و با ثبات توسعه می یابند. هیچ گونه تصادفی بودنی در الگوی پایه در نظر گرفته نخواهد شد.
کلاس دوم : تقریبا تمام الگوهای پایه که به سرعت به یک ساختار با ثبات و یا نوسانی توسعه می یابند. برخی از موارد تصادفی ، در این الگوی پایه در نظر گرفته نمی شود اما برخی از آن ها نیز لحاظ می گردد. تغییرات محلی بر روی الگوی پایه ، تمایل دارند به صورت محلی باقی بمانند.
کلاس سوم : تقریبا تمام الگوهای اولیه که به صورت شبه تصادفی و بی نظم توسعه می یابند. هرگونه ساختار با ثباتی که ظاهر شوند به سرعت توسط نویزهای اطراف از بین خواهند رفت. تغییرات محلی در الگوی پایه تمایل دارند به صورت نامحدودی منتشر شوند .
کلاس چهارم : تقریبا تمام الگوهای اولیه که به ساختارهایی با روش های پیچیده و جالب تعامل و با شکل گیری ساختار های محلی که قادر به زنده ماندن برای مدت طولانی هستند ، توسعه پیدا میکنند. کلاس نوع دوم ، ساختار های با ثبات و یا نوسانی ، ممکن است در نهایت به نتیجه برسند ، اما تعداد گام های مورد نیاز برای رسیدن به این حالت ، ممکن است بسیار زیاد باشد ، حتی اگر الگوی پایه نسبتا ساده باشد.تغییرات محلی بر روی الگوی پایه ممکن است به صورت نامحدودی منتشر گردد. ولفرم تخمین زده است که اگر نگوییم همه ، بسیاری از اتوماتا های سلولی کلاس 4 ، قادر به انجام محاسبات جهانی می باشند. این مساله برای 110 قانون و بازی زندگی مطرح شده توسط کانوی ، اثبات گردیده است.
این تعاریف در طبیعت به صورت کیفی بوده و فضاهایی به منظور تفسیر آن وجود دارد. بر اساس نظریه ولفرم ، "...با تقریبا هر الگوی طبق بندی عمومی ، موارد اجتناب ناپذیری وجود دارند که به یک کلاس با یک تعریف و به کلاس دیگر با تعریف دیگری اختصاص داده می شوند. بنابراین این مساله در اتوماتای سلولی وجود دارد که : قانون های وابسته موقعیتی وجود دارند که برخی ویژگی های یک کلاس و برخی ویژگی های کلاس دیگری را نمایش میدهند. طبقه بندی مطرح شده توسط ولفرم ، به صورت تجربی با یک خوشه بندی از خروجی طول فشرده اتوماتای سلولی منطبق است.
با الهام از طبقه بندی مطرح شده توسط ولفرم تلاش های متعددی به منظور طبقه بندی اوتاماتای سلولی در کلاس های فرمال دقیق وجود داشته است. به عنوان نمونه ، کولیک و یو سه کلاس خوش تعریف (و یک کلاس چهارمی برای اتوماتا که با هیچ کدام از این ها منطبق نیست) را مطرح نمودند. این کلاس ها برخی اوقات با نام کلاس های کولیک-یو نام برده می شوند. به اثبات رسیده است که عضویت در این کلاس ها تصمیم ناپذیر است. کلاس 2 طبقه بندی ولفرم را میتوان به دو زیر گروه قانون های با ثبات (ثابت) و نوسانی (پریودیک) تقسیم بندی نمود.
برگشت پذیر
یک اتوماتای سلولی معکوس پذیر است اگر برای هر پیکربندی جاری اتوماتای سلولی ، دقیقا یک پیکربندی قبلی (پیش تصویر) وجود داشته باشد. اگر یک تفکر در مورد اتوماتای سلولی این باشد که یک تابع به منظور نگاشت پیکربندی به پیکربندی است ، به صورت معکوس پذیر نشان میدهد که این تابع یک به یک است. اگر یک اتوماتای سلولی معکوس پذیر باشد ، رفتار زمان معکوس آن نیز میتواند به عنوان یک اتوماتای سلولی توصیف گردد. این حقیقت از نتایج قضیه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) که در رابطه با ویژگیهای توپولوژیکال اتوماتای سلولی است، می باشد. برای اتوماتای سلولی که در آن هر پیکربندی یک پیش تصویر ندارد ، پیکربندی های بدون پیش تصویر الگوهای پیوسته و متراکم ادن (به انگلیسی: Garden of Eden) نامیده می شوند.
برای اتوماتای تک بعدی ، الگوریتم های شناخته شده ای به منظور تشخیص معکوس پذیری با معکوس ناپذیری یک قانون وجود دارد. با این حال ، برای اتوماتای های دو بعدی یا چند بعدی معکوس پذیری تصمیم ناپذیر است ، بدین معنا که ، الگوریتم یوجود ندارد که به عنوان ورودی یک قانون اتوماتا دریافت نموده و تضمین کند که میتواند به صورت درستی معکوس پذیری آن را تعیین نماید. اثبات مطرح شده توسط جارکو کری به مشکل کاش کاری موجود در مدل ونگ تایلز مرتبط است.
اتوماتای سلولی معکوس پذیر ، اغلب به منظور شبیه سازی پدیده های فیزیکی مانند مباحث حرکتی گاز و مایع مورد استفاده قرار میگیرد. زیرا آن ها از قوانین ترمودینامیک پیروی میکنند. چنین اتوماتای سلولی قانون هایی دارد که به صورت ویژه به گونه ای ساخته شده اند که معکوس پذیر باشد.چنین سیستم هایی توسط نرمن مارگولس و توماس توفولی و دیگران مورد مطالعه قرار گرفته است. تکنیک های متعددی می تواند به منظور ساخت صریح اتوماتای سلولی معکوس پذیر با معکوس های شناخته شده ، مورد استفاده قرار بگیرد. دو نوع متداول از این تکنیک ها ،اتوماتای سلولی مرتبه دوم (به انگلیسی: second order cellular automaton) و اتوماتای سلولی بلاکی (به انگلیسی: block cellular automaton) می باشند. هر دو اینها بیانگر تعریف هایی از طرق مختلف برای یک اتوماتای سلولی هستند. هرچند چنین اتوماتایی تعریف بیان شده در بالا را کاملا بر آورده نمی کند ، میتواند نشان دهد که آنها میتوانند با اتوماتای سلولی متعارف با تعداد همسایگی و تعداد حالت های به اندازه کافی بزرگ شبیه سازی شوند ، و بنابراین میتواند بعنوان زیرمجموعه ای از اتوماتای سلولی متعارف مطرح گردد. بطور عکس ، میتواند نشان داده شود که هر اتوماتای سلولی معکوس پذیری میتواند با یک اتوماتای سلولی بلاکی شبیه سازی شود.
تک گرایی
یک کلاس خاص از اتوماتای سلولی ، اتوماتای سلولی تک گرایی (به انگلیسی: Totalistic) است . حالت هر سلول در اتوماتای سلولی تک گرا به وسیله یک عدد نشان داده می شود. (معمولا یک عدد صحیح گرفته شده از یک مجموعه متناهی) ، و مقدار یک سلول در زمان t فقط به مجموع مقادیر سلول های موجود در همسایگی آن در زمان t-1 بستگی دارد. (احتمالا از جمله خود آن سلول). اگر حالت سلول در زمان t به مقدار خودش در زمان t-1 وابسته باشد ، این اتوماتای سلولی ، تک گرای خارجی نامیده میشود. بازی زندگی مطرح شده توسط کانوی یک نمونه از اتوماتای فوق با مقادیر 0 و 1 برای سلول ها است. اتوماتای سلولی تک گرای خارجی با ساختار همسایگی از نوع مور ، مشابه با زندگی برخی اوقات اتوماتای سلولی زندگی مانند نامیده می شود.
اتوماتای مرتبط
تعمیم های زیادی برای مفهوم اتوماتای سلولی امکان پذیر است. یک راه استفاده از چیز دیگری به جای شبکه چهارخانه است. (مکعبی و غیره) بعنوان مثال ، وقتی طرح کاشی با شش ضلعی های منظم است ، این شش گوشه ها می توانند به عنوان سلول مورد استفاده قرار بگیرند. در بسیاری از موارد ، اتوماتای سلولی حاصل شده ، با اتوماتا هایی با شبکه چهار خانه با طراحی خاص همسایگی و قانون ها ، برابری میکند. نوع دیگر می تواند پیاده سازی نامنظم خود شبکه باشد ، به عنوان مثال مدل پنروس تایل (به انگلیسی: Penrose tiling) .
یک اتوماتای سلولی مبتنی بر سلول های شش گوش. (قانون 34/2)
همچنین ، قانون ها نیز میتوانند احتمالی باشد به جای آنکه قطعی باشند. چنین اتوماتای سلولی ، اتوماتای سلولی احتمالی نامیده می شوند. قانون های احتمالی ، به هر الگو در زمان t ، احتمالاتی به منظور گذر از سلول مرکزی به هر حالت ممکن در زمان t+1 اختصاص میدهند. برخی اوقات ، یک قانون ساده تر مورد استفاده قرار میگیرد. بعنوان مثال : "بازی زندگی یک قانون است ، اما برای هر گام زمانی احتمال 0.001% وجود دارد که هر سلول به رنگ مخالف خود گذر داشته باشد".
همسایگی و یا قانون ها میتوانند در طول زمان یا مکان تغییر کنند. به عنوان مثال ، در ایتدا ، حالت جدید یک سلول می تواند توسط سلول های افقی مجاور تعیین گردد ، اما برای توسعه بعدی می تواند سلول های عمودی مورد استفاده قرار بگیرد.
در اتوماتای سلولی ، حالت جدید سلول ،تحت تاثیر حالت جدید سلول های دیگر نمی باشد. این موضوع می تواند تغییر کند ، به گونه ای که ، بعنوان نمونه ، یک بلاک دو در دو از سلول ها می تواند توسط خود آن سلول و سول های مجاورش تعیین گردد.
اتوماتاهای پیوسته نیز وجود دارد . این ها شبیه اتوماتای سلولی تک گرا هستند ، اما بجای اینکه قانون ها و حالت ها بصورت گسسته(به عنوان مثال ، یک جدول که از حالت های {0,1,2}) باشند ، توابع پیوسته مورد استفاده قرار میگیرد ، و حالت ها بصورت پیوسته می شوند. (معمولا مقادیری در بازه 0,1) و حالت های مکان ، یک تعداد متناهی از اعداد حقیقی می باشد. اتوماتاهای سلولی خاصی میتوانند بر اساس الگوهای شناور مانند این عمل نمایند.
اتوماتای فضایی پیوسته ، یک رشته پیوسته از مکان ها دارد. حالت یک مکان یک تعداد متناهی از یک مجموعه اعداد حقیقی است. زمان هم بصورت پوسته بوده و حالت با توجه به معادلات دیفرانسیل تکامل می یابد. یک نمونه مهم ، ساختارهای واکنش-انتشار می باشد ، معادلات دیفرانسیلی که توسط تورینگ به منظور توضیح نحوه ایجاد هاشور در خر ها و نحوه ایجاد نقاط در پلنگ توسط واکنش های شیمیایی معرفی شد. زمانی که اینها توسط اتوماتای سلولی تقریب زده شده ، آن ها اغلب بر اساس الگوهای مشابه ای عمل می کنند. مک لنان، اتوماتای فضایی پیوسته را به عنوان یک مدل محاسباتی در نظر میگیرد.
مثال های شناخته شده ای برای اتوماتای فضایی پیوسته وجود دارد که پدیده انتشار را مشابه گلایدر های در بازی زندگی نمایش می دهند.
ماشین های سلولی ابتدایی
ساده ترین اتوماتای سلولی مهم می تواند یک بعدی ، با دو حالت امکان پذیر برای هر سلول ، که همسایه ها ، سلول های مجاور در دو طرف آن تعریف می شود ، می باشد. یک سلول و دو همسایه آن ، همسایگی از سه سلول را می سازند. بنابراین 8 الگوی ممکن برای همسایگی وجود دارد. یک قانون شامل تصمیم گیری برای هر الگوست که تعیین میکند در توسعه بعدی سلول باید 0 باشد یا 1.
بر این اساس 256 قانون امکان پذیر وجود دارد. این 256 اتوماتای سلولی به طور کلی بر اساس کد ولفرم آنها (یک قرداد نامگذاری استاندارد که توسط ولفرم مطرح شد. این استاندارد به هر قانون یک عدد از 0 تا 255 تخصیص میدهد ) ارجاع داده می شوند. تعدادی از مقالات به تحلیل و مقایسه این 256 اتوماتای سلولی پرداخته اند. اتوماتای سلولی قانون 30 و 110 رولی به طور خاص ، جالب هستند. تصویر زیر ، سابقه هر کدام را زمانی که پیکر بندی آغازین شامل یک 1 (در قسمت بالای هر تصویر ) که توسط 0 ها احاطه شده است ، نشان می دهد. هر ردیف از پیکس ها ، یک توسعه را در سابقه اتوماتا نشان می دهد ، t=0 بالاترین ردیف می باشد. هر پیکسل 0 با رنگ سفید و هر پیکسل 1 با رنگ سیاه ، رنگ آمیزی شده است.
اتوماتای سلولی 30 قانونی
اتوماتای سلولی 110 قانونی
مدل 30 قانونه رفتار کلاس 3 را نمایش می دهد. بدین معنا که الگوهای ساده مشابه آنچه نشان داده شده ، منجر به ایجاد سوابقی بی نظرم و ظاهرا تصادفی می گردند. مدل 110 قانونه، مشابه بازی زندگی، چگونگی رفتار چیزی که ولفرم آن را کلاس 4 نامیده است را نشان می دهد که رفتاری نه کاملا تصادفی و نه کاملا تکراری دارند. ساختارهای محلی ظاهر می شوند و از راه های جستجوی پیچیده مختلف با یکدیگر تعامل میکنند. در طی توسعه کتاب جنبه جدید از علوم ، همانطوری که دستیار تحقیقاتی ولفرم در سال 1994 ، متیو کوک اثبات نموده بود که برخی از این ساختار ها به اندازه کافی قوی هستند که بتواند جامعیت (عمومیت) را پشتیبانی کنند. این نتیجه جالب است زیرا 110 قانونه یک سیستم تک بعدی کاملا ساده و سیستمی است که برای یک مهندس انجام چینین رفتار خاصی مشکل است.
بنابراین این نتیجه حمایت قابل توجهی را برای دیدگاه ولفرم که سیستم های کلاس 4 ، به نظر میرسد به طور ذاتی یک سیستم جهانی باشند ، فراهم آورد. کوک اثبات خود را در یک کنفرانس اتوماتای سلولی مؤسسه سنتا فه در سال 1998 مطرح نمود اما ولفرم مانع از قرارگیری این اثبات در مجموعه مقالات کنفرانس گردید. زیرا ولفرم نمیخواست که پیش از انتشار کتاب جنبه جدید از علوم این اثبات انتشار پیدا کند. در سال 2004 ، اثبات کوک سرانجام در ژورنال ولفرم (سری 15 ، شماره 1) منتشر شد، ده سال پس از زمانی که کوک آن را مطرح نموده بود. 110 قانونه شامل پایه هایی می شود که برخی از کوچکترین ماشین های تورینگ جهانی بر اساس آن ساخته شده اند.
فضای قانون
قانون ابتدایی اتوماتای سلولی ، توسط 8 بیت مشخص شده است ، و همه قانون های ابتدایی اتوماتای سلولی میتوانند بر روی روئوس یک واحد ابر مکعب هشت بعدی در نظر گرفته شوند. این واحد ابر مکعب فضای قانون اتوماتای سلولی می باشد. برای نزدیکترین همسایه بعدی اتوماتای سلولی ، یک قانون با 32 بیت مشخص می گردد، و فضای قانون اتوماتای سلولی یک واحد ابرمکعب 32 بعدی می باشد. فاصله میان دو قانون ، می تواند به وسیله تعداد گام های مورد نیاز برای حرکت از یک راس ، که قانون اول را مشخص می کند ، به راس دیگر ، که قانون دیگر را مشخص می کند ، در امتداد لبه ابر کعب ، مشخص شود. این فاصله قانون تا قانون همچنین فاصله همینگ نیز نامیده می شود.
فضای قانون اتوماتای سلولی به ما اجازه می دهد که بپرسیم آیا قانون هایی با رفتار پویای مشابه در نزدیکی هم قرار دارند یا خیر. از نظر گرافیکی ، ترسیم یک ابر مکعب با تعداد بعد زیاد ، در یک صفحه دو بعدی یک کار دشوار باقی مانده است ، و یک مکان یاب خام یک قانون در ابرمکعب ، بیت شماره 1 در میان رشته 8 بیتی مربوط به قانون مقدماتی (و یا رشته 32 بیتی برای قانون های نزدیکترین همسایه بعدی ) می باشد. ترسیم قانون ها در کلاس مختلف مدل ولفرم در این چنین برش هایی از فضای قانون ، نشان می دهد که قانون های کلاس 1 ، متمایل به داشتن تعداد کمتری از بیت 1 هستند ، در نتیجه در یک ناحیه از فضا قرار دارند. در حالی که قانون های کلاس 3 ، تمایل به داشتن تعداد بیت 1 با نسبتی بیشتر از 50 درصد دارند.
برای فضای قانون های بزرگتر اتوماتای سلولی ، نشان داده شده است که قانون های کلاس 4 ، در موقعیتی بین کلاس 1 و 3 قرار گرفته اند. این مشاهدات پایه و اساس اصطلاح کناره های بی نظمی و یاد آور انتقال فاز در ترمودینامیک می باشد.
زیست شناسی
یک الگوی اتوماتای سلولی را در سطح خود نمایش می دهد.
برخی از فرآیندهای زیستی بر اساس اتوماتای سلولی اتفاق افتاده و یا میتوانند شبیه سازی شوند. الگوی برخی از صدف ها ، شبیه صدف های نوع کانوس و سیمبیولا ، توسط اتوماتای سلولی طبیعی تولید شده اند. سلول های رنگدانه ای در یک نوار باریک در لبه پوسته آن ها قرار دارند. هر سلول با پیروی از یک نسخه طبیعی از قوانین ریاضی، با توجه به فعال یا غیر فعال بودن سلول های رنگدانه ای همسایه اش ، رنگدانه ترشح می کند. نوار سلول الگوی رنگی را همانطوری که پوسته یه ارامی در حال رشد است، بر روی آن قرار می دهد. به عنوان مثال ، گونه گسترده تر کانوس، یک الگوی مشابه با اتوماتای 30 قانونه مدل ولفرم را در بر دارد.
گیاهان مصرف و از دست دادن گازها (بخارها) را از طریق یک مکانیزم ماشین سلولی تنظیم می نمایند. هر روزنه در برگ به عنوان یک سلول عمل می کند.
الگوهای امواج متحرک بر روی سطح سفالوپودها را می توان با یک اتوماتای سلولی دو بعدی دو حالته شبیه سازی نمود. هر حالت بر اساس یک کراماتوفر توسعه یافته و یا لغو شده است.
اتوماتای آستانه ای به منظور شبیه سازی نورون ها ایجاد گردید و با به کارگیری آن رفتارهای پیچیده مانند شناخت و یادگیری قابل شبیه سازی می باشد.
فیبروبلاست ها شباهت هایی با اتوماتای سلولی دارند، بدین صورت که هر فیبروبلاست فقط با هماسیگان خود تعامل دارد.
انواع شیمیایی
واکنش بلوسوف-ژابوتینسکی یک اوسيلاتور شیمیایی فضا-زمانی است که می تواند با روش های اتوماتای سلولی شبیه سازی شود. در دهه 50 میلادی ، ژابوتینسکی ، (کار بلوسوف را گسترش داد) کشف کرد که هنگامی که یک لایه همگن نازک از مخلوطی از مالونیک اسید ، برمات اسیدی و نمک سریک با هم مخلوط شده و در سکون قرار داده می شوند ، طرح های هندسی جذاب مانند دایره متحد المرکز و مارپیچی در سراسر آن منتشر می شوند. الکساندر ددنی ، در بخش "Computer Recreations" از شماره آگوست سال 1988 مجله ساینتیفیک آمریکن ، یک ماشین سلولی که توسط که توسط مارتین گرهارد و هایک شوستر از دانشگاه بیلفد (آلمان غربی) توسعه داده شد مورد بحث قرار داد. این اتوماتا الگوهای موجی شبیه آنچیزی که در واکنش بلوسوف-ژابوتینسکی است ، تولید می نماید.
کاربرد ها
پردازنده های کامپیوتر
پردازنده های اتوماتای سلولی پیاده سازی فیزیکی مفاهیم CA هستند ، که میتواند اطلاعات را از بعد محاسباتی پردازش نماید. مولفه های پردازش ها در یک شبکه منظم از سلول های یکسان سازماندهی شده اند. این شبکه معمولا یک کاشی کاری مربعی، و یا موزاییک کاری، از دو یا سه بعد می باشد. سایر انواع کاشی کاری نیز امکان پذیر است ولی هنوز مورد استفاده قرار نگرفته است. حالت های سلول فقط به وسیله تعامل آن با همسایگان مجاورش مشخص می شود. هیچ راهی برای برقراری ارتباط مستقیم با سلول های دورتر وجود ندارد. یکی از نمونه های چنین پردازنده اتوماتای سلولی پیکربندی آرایه ، آرایه های سیستولیک می باشد. تعاملات سلولی می تواند از طریق بار الکتریکی ، مغناطیس ؛ ارتعاشات (فونون در مقیاس کوانتومی) و یا هر روش فیزیکی دیگری انجام پذیرد. این مساله می تواند از طرق مختلفی انجام گیرد بنابراین هیچ اتصال سیمی میان مولفه ها نیاز نیست. این پردازنده با پردازنده هایی که امروزه در بیشتر کامپیوتر ها مورد استفاده قرار میگیرند (طراحی ون نیومن) کاملا متفاوت است. در طراحی ون نیومن ، پردازنده به بخش ها به همراه مولفه هایی تقسیم شده است که می توانند با مولفه های راه دور از طریق سیم ها ، ارتباط برقرار نمایند.
رمز نویسی
مدل ۳۰ قانونه در اصل بعنوان یک رمز گذار بلوکی امکان پذیر برای استفاده در رمزگذاری قطعه‌ای پیشنهاد گردید. اتوماتای سلولی دو بعدی برای تولید عدد تصادفی مورد استفاده قرار گرفته است. اتوماتای سلولی برای رمزنگاری کلید عمومی ارائه شده است . تابع یک طرفه ، تکامل یک CA متناهی است که یافتن معکوس آن به نظر دشوار میرسد. با توجه به قانون، هر کسی می تواند به راحتی حالت های آینده را محاسبه نماید، اما به نظر می رسد که محاسبه حالت های قبلی بسیار دشوار باشد.
کد های تصحیح خطا
مدل اتوماتای سلولی (به انگلیسی: CA) به منظور طراحی کدهای تصحیح خطا در مقاله "Design of CAECC – Cellular Automata Based Error Correcting Code" مورد استفاده قرار گرفته است. این مقاله یک طرح جدید از ساختن کدهای همینگ SEC-DED با استفاده از CA را توصیف نموده است. و همچنین گزارشی از یک رمزگشای سخت افزاری سریع نیز در این مقاله آمده است.
مدل سازی واقعیت های فیزیکی
همانگونه که آندر ایلاچینسکی در اتوماتای سلولی خود اشاره نمود، بسیاری از محققین این سوال را مطرح نموده اند که آیا جهان یک اتوماتای سلولی است.او استدلال می کند که اهمیت این سوال ممکن است با یک مشاهده ساده ، بهتر مشخص گردد، این مشاهده می تواند به شرح زیر بیان گردد.
سیر تکاملی 10 قانونه را در نظر بگیرید : اگر این قانون یک نوع فیزیک خارج از بعد باشد، توصیف مناسب الگوهای مشاهده شده چه خواهد بود؟ اگر یک ناظر نداند که چگونه تصاویر تولید شده است، او ممکن است در نهایت بتواند حدس هایی در مورد حرکت برخی اشیای ذره مانند بیان نماید. یک فیزیکدان به نام جیمز کراچفیلد بر مبنای این ایده یک تئوری ریاضی دقیق مطرح نمود که پیدایش آماری از ذرات ، از اتوماتای سلولی را اثبات می کند. در آن زمان ، همانگونه که این استدلال به پیش می رود ، مساله تعجب آور می تواند این باشد که جهان که در حال حاضر به وسیله فیزیک و با اشیای ذره مانند (فیزیک ذرات) توصیف می شود، می تواند یک اتوماتای سلولی در پایه ای ترین سطح آن باشد. در حالی که تئوری کامل در این زمنیه همچنان در حال توسعه است ؛ توسعه این فرضیه ، محققان را بر آن داشت که حدس و گمان های جالب و شهود های مثمر ثمری را در زمینه چگونگی قابل درک بودن جهان در یک چارچوب گسسته مطرح نمایند. ماروین مینسکی یکی از پیشگامان هوش مصنوعی ، به بررسی چگونگی درک نحوه تعامل ذرات با شبکه اتوماتای سلولی چهار بعدی پرداخت ؛ کنراد تسوزه مخترع اولین کامپیوتر ، Z3 ، یک شبکه منظم به منظور بررسی پرسشی مبنی بر محتوای اطلاعاتی ذرات ، مطرح نمود.اخیرا ادوارد فردکین ، چیزی را که خودش "فرضیه طبیعت محدود" می نامد را به نمایش گذاشت. به عنوان مثال، این ایده که در نهایت هر کمیت فیزیکی، از جمله فضا و زمان، به کیمیت هایی گسسته و محدود تبدیل خواهد شد. فردکین و ولفرم از طرفداران سر سخت فیزیک مبتنی بر اتوماتای سلولی هستند.
در سال های اخیر ، پیشنهادهای دیگری در این زمینه ، در میان مقالات مرتبط با محاسبات غیر استاندارد مطرح گردید. کتاب جنبه دیگری از علوم ، اتوماتای سلولی را به عنوان کلیدی برای درک مسایل مختلف شامل فیریک ، در نظر گرفته است. ریاضیات مدلی بر اساس منابع (به انگلیسی: Mathematics of the Models of Reference)، یک جهان اصلی دو بعدی /سه بعدی مبتنی بر یک شبکه "لوزی دوازده وجهی" جدید و یک قانون منحصر به فرد را نشان داد. این مدل عمومیت (جامعیت) را تامین نموده (این مدل با ماشین تورینگ برابری می کند)، معکوس پذیری را کامل نموده (یک ضرورت که اگر کسی خواست بتواند کمیت های متعددی را ذخیره کند و اطلاعات از بین نرود) و در نظریه مرتبه اول گنجانده شده است که اجازه محاسبه عبارات کیفی در مورد تکامل جهان را داده است.