موضوع مقاله: اتوماتای سلولی ساده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اتوماتای سلولی ساده | مقدمه: اتوماتای سلولی ساده در ریاضیات و نظریه محسابات، جزو اتوماتای سلولی یک بعدی می‌باشد به نحوی که مجموعه حالات فقط متشکل از دو حالت (۰ یا ۱) و قاعده تعیین حالت یک سلول در گام بعدی، فقط تابعی از حالت فعلی خود آن سلول و دو همسایه مجاورش باشد. | ## بخش 1: اتوماتای سلولی ساده | این سیستم یکی از ساده‌ترین سیستم‌های محاسبه می‌باشد، با این وجود، یکی از این سیستم‌ها موسوم به قاعده ۱۱۰ هم ارز ماشین محاسبه تورینگ می‌باشد. به این معنی که هر محاسبه ای که بر روی ماشین تورینگ قابل انجام باشد، بر روی قاعده ۱۱۰ هم قابل انجام است. او برای اولین بار نتایج خود را به صورت جامع در کتاب نوع جدیدی از علم منتشر کرد که بررسی حالت‌های مختلف اتوماتای سلولی ساده بخشی از آن کتاب بود. قاعده اتوماتون ساده، باید به ازای هر کدام از این حالت‌های پیکربندی، حالت بعدی سلول را تعیین کند و این به این معنی است که ۲۵۶ = ۲۲۳ اتوماتای سلولی ساده ممکن وجود دارد. ولفرم در کتابش و قبل تر در مقاله ای، روشی برای شماره گزاری این ۲۵۶ حالت از ۰ تا ۲۵۵ ابداع کرد که به این شکل است که ابتدا پیکر بندی‌های مختلف را بر حسب اندازه مرتب می‌کنیم (مثلاً ۱۱۱ بزرگترین پیکربندی است و ۰۰۰ کوچکترین پیکربندی) و حالت بعدی سیستم به ازای آن پیکر بندی را می‌نویسیم (هر حالت ۰ یا ۱ است). به این ترتیب هشت حالت ممکن کنار هم قرار می‌گیرند و یک عدد مبنای ۲ با ۸ رقم را تشکیل می‌دهند، مقدار آن عدد را در سیستم ده دهی شماره آن اتوماتا می‌نامیم. مثال زیر برای قاعده ۱۱۰ می‌باشد و L,C,R نشانگر چپ، وسط، راست هستند و حالت هر کدام از سلول‌های پیکر بندی را مشخص می‌کنند: ۱۱۱ ۱۱۰ ۱۰۱ ۱۰۰ ۰۱۱ ۰۱۰ ۰۰۱ ۰۰۰ پیکربندی فعلی (L,C,R) ۰ ۱ ۱ ۰ ۱ ۱ ۱ ۰ حالت بعدی سلول میانی N۱۱۰d=(C+R+C*R+L*C*R)%۲ حالات هم ارز هر چند ۲۵۶ قاعده برای اتوماتای سلولی ساده داریم، اما بعضی از این حالت‌ها با هم مشابه هستند. | ## بخش 2: اتوماتای سلولی ساده | اهمیت همچین تقارنی در این است که اگر دو قاعده با یک تقارن به هم تبدیل شوند از نظر پیچیدگی محاسباتی هم ارز هستند زیرا پیچیدگی محاسباتی نسبت به این تقارن ناوردا است. یک راه دیگر برای تعریف رده هم‌ارزی بر روی این ۲۵۶ حالت، تعریف حالت‌های مکمل می‌باشد. اگر در یک قاعده همه ۰ و ۱ها را برعکس کنیم باز هم پیچیدگی محاسباتی سیستم عوض نمی‌شود. (به زبان ریاضی، نقطه ثابت‌های تبدیل ذکر شده هستند) همچنین ترکیب دو تبدیل بالا (انعکاس و مکمل منطقی) هم خود یک تبدیل جدید به ما می‌دهد که پیچیدگی تحت آن ناوردا است. رفتار سیستم تحت حالت اولیه تصادفی یک راه بررسی این اتوماتا این است که برای شرایط اولیه تصادفی، رفتار آن‌ها را بررسی کنیم. ولفرم آن‌ها را به چهار دسته کلی تقسیم‌بندی کرده‌است: دسته اول: این اتوماتا به حالت یکنواخت همگرا می‌شوند. یعنی پس از چند گام به حالتی می‌رسیم و دیگر تغییر نمی‌کند، یا به یک چرخه محدود می‌رسیم که بین تعداد محدودی پیکربندی می‌چرخد. | ## بخش 3: اتوماتای سلولی ساده | دسته سوم: این اتوماتا به حالت خاصی نمی‌رسند و به نظر می‌رسد رفتار سیستم تصادفی می‌ماند. دسته چهارم: در این دسته به بازه‌هایی می‌رسیم که تکرار شونده هستند یا پایدارند ولی همچنین ساختارهایی ایجاد می‌شوند که با سازوکارهای نابدیهی با هم برهم کنش می‌کنند. کاربردها بررسی اتوماتای سلولی ساده، هم از منظر نظری (در حوزهٔ ریاضیات و علوم کامپیوتر) و هم کاربردی مورد توجه است. از کاربردهای عملی این سیستم‌های می‌توان به کار عبدو (دانشگاه منوفیه مصر) و همکارانشان اشاره کرد که بر مبنای این اتوماتا، روشی برای رمزنگاری ابداع کردند. بطور خاص الگوریتم ابداع شده توسط آن‌ها روشی برای رمزنگاری تصویر است که ادعا می‌شود در مقابل حملات تفاضلی و آماری مقاوم است. | ## جمع‌بندی | از منظر نظری هم می‌توان به کار کاتانیو اشاره کرد که اتوماتای سلولی ساده را از نگاه توپولوژیکی بررسی کرده، و به برآمدن آشوب در این سیستم‌ها پرداخته‌است.