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

اتوماتای سلولی مدلی از ریاضیات گسسته است که در مباحثی چون نظریه محاسبه پذیری، ریاضیات، فیزیک، سامانه های انطباقی پیچیده، زیست شناسی نظری و ریز ساختارها مورد مطالعه قرار گرفته است. اتوماتای سلولی با نام هایی مانند فضاهای سلولی، اتوماتای مفروش سازی، ساختارهای همگن، ساختارهای سلولی، ساختارهای مفروش سازی و آرایه های تکرار شونده نیز بیان می گردد.
یک اتوماتای سلولی شامل یک شبکه منظم از سلول ها است که هر کدام از آن ها در یکی از حالات از مجموعه حالات متناهی امکان پذیر قرار دارند. مانند on و offیا مقدار منطقی 0 و 1. همچنین شبکه می تواند هر بعد متناهی داشته باشد. برای هر سلول، یک مجموعه از سلول ها که همسایهٔ آن نامیده می شود، نسبت به آن سلول مشخص تعریف شده است. یک حالت آغازین ( time = ۰ ) یا ( t=0 ) با تخصیص دادن یک وضعیت به هر سلول انتخاب می شود. یک نسل جدید ( توسعه t به وسیله ۱ ) ، بر اساس یکسری قوانین ثابت ( عموماً یک تابع ریاضی ) که وضعیت جدید برای هر سلول را بر اساس وضعیت جاری آن سلول و وضعیت های سلول های همسایه آن، مشخص می کند، تولید می شود. به طور معمول، قوانین به روزرسانی وضعیت سلول ها برای هر سلول مشابه است و در طول زمان تغییر نمی کند، و به کل شبکه به صورت هم زمان اعمال خواهد شد، هر چند استثناهایی نیز وجود دارد، مانند اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام.
این مفهوم در ابتدا در دهه ۴۰ میلادی، به وسیله استنی سواف اولام و جان فون نویمان در حالی که آن ها در آزمایشگاه ملی لس آلاموس بودند، کشف شد. این موضوع در دهه ۵۰ و ۶۰ میلادی نیز توسط برخی مورد مطالعه قرار گرفت ولی تا دهه ۷۰ و مطرح شدن بازی زندگی کانوی، یک اتوماتای سلولی دو بعدی، که علاقه به این موضوع را به ابعادی فراتر از بحث های دانشگاهی گسترش داد، هنوز وجود نداشت. در دهه ۸۰، استیون ولفرم، که درگیر مطالعه سیستماتیک یک اتوماتای تک بعدی یا چیزی که او اتوماتای سلولی بنیادی می نامید، بود، دستیار تحقیقاتی او متیو کوک نشان داد که یکی از این قوانین، کامل بودن تورینگ است. ولفرم مقاله ای با عنوان جنبه دیگری از علوم ( به انگلیسی: A New Kind of Science ) را در سال ۲۰۰۲ منتشر نمود. او در این مقاله مدعی شد اتوماتای سلولی در بسیاری از حوزه های علوم کاربرد دارد. از جمله آن ها می توان به کاربرد آن در پردازنده های کامپیوتری و رمزنگاری اشاره کرد.