اتوماتای سلولی
تاریخچه

استنی‌سواف اولام، زمانی که در آزمایشگاه ملی لس آلاموس، در دهه ۴۰ میلادی مشغول به کار بود، بر روی رشد کریستال‌ها با به‌کارگیری یک مدل شبکه توری منظم به عنوان مدل خود، مطالعه می‌نمود. در همان زمان، جان فون نویمان، همکار اولام در لس آلاموس، بر روی مشکلات سیستم‌های خود تکرار یا همان خودجایگزین‌گری کار می‌کرد. طراحی اولیه ون نیومن بر اساس ساخته شدن یک ربات توسط یک ربات دیگر بنا نهاده شد. این طراحی به عنوان مدل حرکتی شناخته می‌شود. در روند توسعه این طراحی، ون نیمن متوجه مشکل بزرگی در زمینه ساخت یک روبات خود تکرار شد، و هزینه بالای در تولید ربات به همراه دریایی از قطعات که برای ساخت تکرارش نیاز دارد نیز از دیگر مشکلات است. نیومن یک مقاله با عنوان «نظریه منطقی و عمومی اتوماتا» در سال ۱۹۴۸ در نشست هیگزون مطالعه کرد. اولام کسی بود که پیشنهاد استفاده از یک سیستم گسسته برای ایجاد یک مدل کاهش یافته از مدل خود تکرار را مطرح نمود. نیلز آل باریچرلی بسیاری از کشفیات اولیه در زمینه این مدل‌های زندگی مصنوعی را انجام داده‌است.
اولام و ون نیومن یک متد به منظور محاسبه حرکت مایع در اواخر دهه ۵۰ میلادی ایجاد نمودند. مفهوم مؤثر این متد در نظر گرفتن مایع به عنوان گروهی از واحدهای گسسته و محاسبه حرکت هر کدام بر اساس رفتار همسایگان خود بوده‌است. بدین سان اولین سیستم اتوماتای سلولی متولد شد. همانند شبکه توری منظم اولام، اتوماتای سلولی طراحی شده توسط ون نیومن به صورت دو بعدی با الگوریتم خود تکرار او پیاده‌سازی شده‌است. نتیجه یک سازنده کپی‌کننده جهانی که با یک اتوماتای سلولی و مجموعه کوچکی از همسایگان. (فقط این سلول‌هایی که با آن‌ها در تماس هستند به عنوان همسایه محسوب می‌شوند، برای اتوماتای سلولی مدل ون نیون، فقط سلول‌های متعامد) و ۲۹ حالت برای هر سلول، بود. ون نیومن یک نظریه اثبات وجود مطرح نمود که یک الگوی مشخص، یک کپی بی پایان از خود را درون جهان سلولی داده شده به وسیله طراحی پیکره بندی ۲۰۰۰۰۰ سلول که بتوانند چنین کاری انجام دهند، ایجاد خواهد نمود. این طراحی با عنوان مدل موزائیک‌کاری (به انگلیسی: Tessellation) شناخته شده‌است و با نام سازنده جهانی ون نیومن نامیده می‌شود.
همچنین در دهه ۴۰ میلادی، نوربرت وینر و آرتور رونزبلاس یک مدل از رسانه‌های تحریک پذیر را با به‌کارگیری برخی ویژگی‌های یک اتوماتای سلولی توسعه دادند. انگیزه اصلی آن‌ها، توصیف ریاضی انتقال ضربه در سیستم‌های قلبی بود. با این وجود مدل آن‌ها یک اتوماتای سلولی نیست زیرا حداقل، انتشار سیگنال در آن پیوسته و جبهه‌های موج به صورت منحنی است. یک مدل اتاماتای سلولی صحیح از رسانه تحریک پذیر توسط گرینبرگ و هستینگ در سال ۱۹۷۸ توسعه یافته و مورد مطالعه قرار گرفت. کار اصلی وینر و رونزبلاس شامل نگرش‌های مختلفی است و همچنان در نشریان مدرن تحقیقاتی در زمینه بی نظمی قلبی و سیستم‌های تحریک پذیر مطرح می‌باشد.
در دهه ۶۰ میلادی اتوماتای سلولی به عنوان بخش مشخصی از سیستم پویا مورد مطالعه قرار گرفت و اتصال آن با مبحث ریاضیاتی از پویایی سمبلیک برای اولین بار محقق گردید. در سال ۱۹۶۹، هدلند نتایج زیادی را مبتنی بر همین دیدگاه گردآوری نمود. چیزی که هنوز هم به عنوان یک مقاله اصلی برای مطالعه ریاضیاتی اتوماتای سلولی در نظر گرفته می‌شود. اساسی‌ترین نتیجه، در توصیف ویژگی‌های نظریه کورتیس-هدلند-لیندون (به انگلیسی: Curtis–Hedlund–Lyndon theorem) در مورد اینکه مجموعه قوانین سراسری اتوماتای سلولی به عنوان مجموعه‌ای از درون دگرگونی‌های پیوسته از فضای تغییر است.
در سال ۱۹۶۹، پیشگام کامپیوتر آلمانی، کنراد تسوزه، کتاب خود را با عنوان فضای محاسبه (به انگلیسی: Calculating Space) منتشر نمود. او در این کتاب مطرح نموده‌است که قوانین فیزیکی جهان توسط طبیعت گسسته شده‌است، و کل جهان خروجی یک محاسبه قطعی در یک ماشین سلولی منفرد است. نظریه تسوزه، بنیانی برای شاخه‌ای علوم با نام فیزیک دیجیتال قرار گرفت.
در دهه ۷۰ میلادی، یک اتوماتای سلولی دو حالتهٔ دوبعدی با نام بازی زندگی (به انگلیسی: Game of Life) به صورت گسترده‌ای شناخته شد، بخصوص در انجمن‌های محاسباتی اولیه. این اوتوماتا توسط جان کانوی اختراع و توسط مارتین گاردنر در مقاله علمی آمریکایی به شهرت رسید. قوانین آن به صورت زیر است: اگر یک سلول دارای دو بلاک همسایه باشد، به همان صورت قبل باقی می‌ماند. اگر سه بلاک همسایه داشته باشد، سیاه می‌شود. در همهٔ شرایط دیگر، آن سلول سفید خواهدشد. بر خلاف سادگی آن، سیستم به تنوع قابل توجهی در رفتار دست پیدا خواهد نمود، که در حال نوسان به صورت رندوم ظاهری یا منظم هست. یکی از آشکاراترین ویژگی‌های بازی زندگی رخ دادن تکرار شوندهٔ گلایدرها (ترتیبی از سلول‌ها که بنا به ضرورت خودشان را در شبکه جابجا می‌کنند) است. این امکان‌پذیر است که به گونه‌ای اتوماتا را سازماندهی نماییم که گلایدرها به منظور انجام محاسبات با یکدیگر تعامل داشته باشند، و پس از تلاش‌های زیاد، این نشان داده شد که بازی زندگی می‌تواند با یک تورینگ ماشین جهانی برابری نماید. این مسئله به عنوان یک موضوع تفریحی تصور شده و کارهای بسیار کمی خارج از چارچوب بررسی خصوصیات بازی زندگی و اندک قوانین مرتبط با آن در دهه ۷۰ میلادی انجام پذیرفت.
استیون ولفرم به صورت مستقل کار بر روی اتوماتای سلولی را در اوسط سال ۱۹۸۱، پس از بررسی الگوهای پیچیده در طبیعت و نحوه شکل‌گیری آن‌ها بر خلاف قانون دوم ترمودینامیک، آغاز نمود. تحقیقات او در ابتدا با تمرکز بر روی سیستم‌های مدلسازی مانند سیستم‌های عصبی آغاز شده بود. او اولین مقاله اش را در ژورنال Reviews of Modern Physics که تحقیق و بررسی بر روی اتوماتای سلولی پایه (به‌طور خاص اتوماتای ۳۰ قانونه) بود، در سال ۱۹۸۳ منتشر نمود. پیچیدگی غیرقابل انتظار در رفتار چنین قانون‌هایی، ولفرم را به این جهت سوق داد که به این موضوع شک کند که پیچیدگی موجود در طبیعت نیز ناشی از مکانیزم مشابه‌ای باشد. با این وجود، تحقیقات او موجب شد، او دریابد که اتوماتای سلولی سیستم مدلسازی ضعیفی به منظور مدلسازی سیستم‌های عصبی محسوب می‌شود. علاوه بر این، در طی این همین زمان، ولفرم مفاهیم ذاتاً تصادفی بودن و تقلیل ناپذیری را فرموله بندی نموده و پیشنهاد داد که اتوماتای ۱۱۰ قانونه ممکن است همگانی باشد - این حقیقت بعداً توسط متیو کوک، دستیار تحقیقاتی ولفرم، در سال ۱۹۹۰ اثبات گردید.
در سال ۲۰۰۲، ولفرم یک مستند ۱۲۸۰ صفحه‌ای با نام جنبه جدید از علوم (به انگلیسی: A New Kind of Science) منتشر نمود. در این متن، ولفرم در مورد اینکه اکتشافات انجام شده در زمینه اتوماتای سلولی حقایق مجزا و منحصر به فردی نیستند ولی قدرتمند بوده و برای همهٔ رشته‌های علمی پراهمیت هستند، استدلال‌های گسترده‌ای را مطرح نمود. علی‌رغم سردرگمی زیاد مطبوعات، این کتاب در مورد نظریه اساسی فیزیک مبتنی بر اتوماتای سلولی استدلالی مطرح نمی‌نماید. هر چند این کتاب تعداد کمی از مدل‌های خاص فیزیکی مبتنی بر اتوماتای سلولی را توصیف می‌نماید و همچنین مدل‌هایی مبتنی بر سیستم‌های انتزاعی با کیفیت‌های متفاوت، ارائه می‌نماید.