اتوماتای سلولی ساده ( به انگلیسی: Elementary cellular automata ) در ریاضیات و نظریه محسابات، جزو اتوماتای سلولی یک بعدی می باشد به نحوی که مجموعه حالات فقط متشکل از دو حالت ( ۰ یا ۱ ) و قاعده تعیین حالت یک سلول در گام بعدی، فقط تابعی از حالت فعلی خود آن سلول و دو همسایه مجاورش باشد. این سیستم یکی از ساده ترین سیستم های محاسبه می باشد، با این وجود، یکی از این سیستم ها موسوم به قاعده ۱۱۰ هم ارز ماشین محاسبه تورینگ می باشد. به این معنی که هر محاسبه ای که بر روی ماشین تورینگ قابل انجام باشد، بر روی قاعده ۱۱۰ هم قابل انجام است. [ ۱]
بررسی و دسته بندی این سیستم ها کار استیون ولفرم می باشد. او برای اولین بار نتایج خود را به صورت جامع در کتاب نوع جدیدی از علم[ ۱] منتشر کرد که بررسی حالت های مختلف اتوماتای سلولی ساده بخشی از آن کتاب بود.
برای پیکربندی هر سلول و همسایه هایش، ۸ حالت ممکن وجود دارد. قاعده اتوماتون ساده، باید به ازای هر کدام از این حالت های پیکربندی، حالت بعدی سلول را تعیین کند و این به این معنی است که ۲۵۶ = ۲۲۳ اتوماتای سلولی ساده ممکن وجود دارد. ولفرم در کتابش و قبل تر در مقاله ای، روشی برای شماره گزاری این ۲۵۶ حالت از ۰ تا ۲۵۵ ابداع کرد که به این شکل است که ابتدا پیکر بندی های مختلف را بر حسب اندازه مرتب می کنیم ( مثلاً ۱۱۱ بزرگترین پیکربندی است و ۰۰۰ کوچکترین پیکربندی ) و حالت بعدی سیستم به ازای آن پیکر بندی را می نویسیم ( هر حالت ۰ یا ۱ است ) . به این ترتیب هشت حالت ممکن کنار هم قرار می گیرند و یک عدد مبنای ۲ با ۸ رقم را تشکیل می دهند، مقدار آن عدد را در سیستم ده دهی شماره آن اتوماتا می نامیم. [ ۲] مثال زیر برای قاعده ۱۱۰ می باشد و L, C, R نشانگر چپ، وسط، راست هستند و حالت هر کدام از سلول های پیکر بندی را مشخص می کنند:
هر چند ۲۵۶ قاعده برای اتوماتای سلولی ساده داریم، اما بعضی از این حالت ها با هم مشابه هستند. بطور مثال بعضی از قواعد با یک انعکاس به هم تبدیل می شوند. اهمیت همچین تقارنی در این است که اگر دو قاعده با یک تقارن به هم تبدیل شوند از نظر پیچیدگی محاسباتی هم ارز هستند زیرا پیچیدگی محاسباتی نسبت به این تقارن ناوردا است. بطور مثال اگر با این تقارن قاعده ۱۱۰ را تغییر دهیم، به قاعده ۱۲۴ می رسیم. منظور از این تقارن این است که جای حالت XYZ با حالت ZYX عوض شود. از ۲۵۶ قاعده، ۶۴ تا با حالت منعکس یافته برابر هستند. یک راه دیگر برای تعریف رده هم ارزی بر روی این ۲۵۶ حالت، تعریف حالت های مکمل می باشد. اینجا از تقارن بین ۰ و ۱ استفاده می کنیم. اگر در یک قاعده همه ۰ و ۱ها را برعکس کنیم باز هم پیچیدگی محاسباتی سیستم عوض نمی شود. ۱۶ قاعده هم هستند که با مکمل خود یکسان هستند. ( به زبان ریاضی، نقطه ثابت های تبدیل ذکر شده هستند ) همچنین ترکیب دو تبدیل بالا ( انعکاس و مکمل منطقی ) هم خود یک تبدیل جدید به ما می دهد که پیچیدگی تحت آن ناوردا است. ۱۶ قاعده هم هستند که تحت این تبدیل به خودشان نگاشته می شوند. نهایتاً ۸۸ قاعده می ماند که با تبدیلات ذکر شده هم ارز نیستند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبررسی و دسته بندی این سیستم ها کار استیون ولفرم می باشد. او برای اولین بار نتایج خود را به صورت جامع در کتاب نوع جدیدی از علم[ ۱] منتشر کرد که بررسی حالت های مختلف اتوماتای سلولی ساده بخشی از آن کتاب بود.
برای پیکربندی هر سلول و همسایه هایش، ۸ حالت ممکن وجود دارد. قاعده اتوماتون ساده، باید به ازای هر کدام از این حالت های پیکربندی، حالت بعدی سلول را تعیین کند و این به این معنی است که ۲۵۶ = ۲۲۳ اتوماتای سلولی ساده ممکن وجود دارد. ولفرم در کتابش و قبل تر در مقاله ای، روشی برای شماره گزاری این ۲۵۶ حالت از ۰ تا ۲۵۵ ابداع کرد که به این شکل است که ابتدا پیکر بندی های مختلف را بر حسب اندازه مرتب می کنیم ( مثلاً ۱۱۱ بزرگترین پیکربندی است و ۰۰۰ کوچکترین پیکربندی ) و حالت بعدی سیستم به ازای آن پیکر بندی را می نویسیم ( هر حالت ۰ یا ۱ است ) . به این ترتیب هشت حالت ممکن کنار هم قرار می گیرند و یک عدد مبنای ۲ با ۸ رقم را تشکیل می دهند، مقدار آن عدد را در سیستم ده دهی شماره آن اتوماتا می نامیم. [ ۲] مثال زیر برای قاعده ۱۱۰ می باشد و L, C, R نشانگر چپ، وسط، راست هستند و حالت هر کدام از سلول های پیکر بندی را مشخص می کنند:
هر چند ۲۵۶ قاعده برای اتوماتای سلولی ساده داریم، اما بعضی از این حالت ها با هم مشابه هستند. بطور مثال بعضی از قواعد با یک انعکاس به هم تبدیل می شوند. اهمیت همچین تقارنی در این است که اگر دو قاعده با یک تقارن به هم تبدیل شوند از نظر پیچیدگی محاسباتی هم ارز هستند زیرا پیچیدگی محاسباتی نسبت به این تقارن ناوردا است. بطور مثال اگر با این تقارن قاعده ۱۱۰ را تغییر دهیم، به قاعده ۱۲۴ می رسیم. منظور از این تقارن این است که جای حالت XYZ با حالت ZYX عوض شود. از ۲۵۶ قاعده، ۶۴ تا با حالت منعکس یافته برابر هستند. یک راه دیگر برای تعریف رده هم ارزی بر روی این ۲۵۶ حالت، تعریف حالت های مکمل می باشد. اینجا از تقارن بین ۰ و ۱ استفاده می کنیم. اگر در یک قاعده همه ۰ و ۱ها را برعکس کنیم باز هم پیچیدگی محاسباتی سیستم عوض نمی شود. ۱۶ قاعده هم هستند که با مکمل خود یکسان هستند. ( به زبان ریاضی، نقطه ثابت های تبدیل ذکر شده هستند ) همچنین ترکیب دو تبدیل بالا ( انعکاس و مکمل منطقی ) هم خود یک تبدیل جدید به ما می دهد که پیچیدگی تحت آن ناوردا است. ۱۶ قاعده هم هستند که تحت این تبدیل به خودشان نگاشته می شوند. نهایتاً ۸۸ قاعده می ماند که با تبدیلات ذکر شده هم ارز نیستند.
wiki: اتوماتای سلولی ساده