�ݺ�ߣ

1
‫سلولی‬ ‫آتوماتای‬‫کالسیک‬
‫کوشکی‬ ‫امیر‬ ‫مهندس‬ : ‫راهنما‬ ‫استاد‬ / ‫محمودی‬ ‫محمدجواد‬ : ‫دانشجو‬
‫پور‬ ‫شمسی‬ ‫شهید‬ ‫فنی‬ ‫دانشکده‬-‫پاییز‬98
‫؟‬ ‫سلولی‬ ‫آتوماتای‬ ‫چرا‬
‫قرن‬ ‫اواخر‬ ‫در‬0391،‫این‬ ‫نیومن‬ ‫فون‬.‫بسازد‬ ‫خودش‬ ‫پیچیدگی‬ ‫به‬ ‫ماشینی‬ ‫تواند‬ ‫می‬ ‫ماشین‬ ‫یک‬ ‫آیا‬ ‫که‬ ‫داد‬ ‫جواب‬ ‫را‬ ‫سوال‬‫برای‬
،‫مشکل‬ ‫کردن‬ ‫ساده‬.‫اند‬ ‫شده‬ ‫ساخته‬ ‫کوچکتری‬ ‫های‬ ‫بخش‬ ‫از‬ ‫آتوماتاها‬ ‫و‬ ‫ها‬ ‫ماشین‬ ‫گفت‬ ‫او‬‫قطعات‬ ‫از‬ ‫پر‬ ‫مخزن‬ ‫یک‬ ،‫او‬ ‫مدل‬ ‫در‬
‫شناور‬ ‫استفاده‬ ‫مورد‬ ‫های‬ ‫ماشین‬‫که‬‫هستند‬،‫دارد‬ ‫وجود‬.
‫با‬ ‫نیومن‬ ‫فون‬‫آتوماتا‬ ‫سیستم‬ ‫یک‬ : ‫کرد‬ ‫مطرح‬ ‫را‬ ‫قوی‬ ‫استدالل‬ ‫ریاضی‬ ‫منطق‬ ‫از‬ ‫استفاده‬‫را‬ ‫خودش‬ ‫تواند‬ ‫می‬ ‫اولیه‬ ‫طرح‬ ‫داشتن‬ ‫با‬
‫ماشین‬ ‫از‬ ‫کپی‬ ‫یک‬ ‫ساختن‬ ‫برای‬ ‫را‬ ‫اولیه‬ ‫طرح‬ ‫ساختار‬ ‫بعد‬ ‫سازد‬ ‫می‬ ‫اولیه‬ ‫طرح‬ ‫از‬ ‫کپی‬ ‫یک‬ ‫اول‬ : ‫بسازد‬ ‫آتوماتا‬ ‫طور‬ ‫به‬ ‫دوباره‬
‫است‬ ‫کند.جالب‬ ‫می‬ ‫استفاده‬‫که‬DNA‫منط‬ ‫این‬ ‫از‬.‫کند‬ ‫می‬ ‫استفاده‬ ‫خودساختگی‬ ‫ق‬‫کنندگی‬ ‫قانع‬ ‫جهت‬ ‫ساده‬ ‫فرمول‬ ‫یک‬ ‫نیومن‬ ‫فون‬
.‫داشت‬ ‫نیاز‬ ‫بیشتر‬
‫او‬ ‫همکار‬-‫س.اولما‬ ‫پروفسور‬-‫دارد‬ ‫می‬ ‫نگه‬ ‫را‬ ‫محدود‬ ‫های‬ ‫حالت‬ ‫که‬ ‫ها‬ ‫سلول‬ ‫از‬ ‫ای‬ ‫شده‬ ‫آل‬ ‫ایده‬ ‫فضای‬ ‫درباره‬ ‫کردن‬ ‫فکر‬،
‫قس‬ ‫حالت‬ ‫هر‬ ‫که‬ .‫کرد‬ ‫پیشنهاد‬‫م‬‫ت‬‫بر‬ ‫را‬ ‫آتوماتا‬ ‫از‬ ‫مختلفی‬ ‫های‬.‫گرداند‬ ‫می‬
: ‫شد‬ ‫ارائه‬ ‫اولمان‬ ‫توسط‬ ‫وضوح‬ ‫به‬ ‫ای‬ ‫مقاله‬ ‫در‬ ‫ایده‬ ‫این‬
‫نقط‬ ‫هر‬ .‫دارد‬ ‫همسایگانش‬ ‫به‬ ‫اتصال‬ ‫متناهی‬ ‫تعدادی‬ ‫کدام‬ ‫هر‬ ‫که‬ ‫نقاط‬ ‫از‬ ‫نامتناهی‬ ‫معین‬ ‫گراف‬ ‫یا‬ ‫"شبکه‬‫متناهی‬ ‫عدد‬ ‫یک‬ ‫مستعد‬ ‫ه‬
‫زمان‬ ‫در‬ ‫ها‬ ‫همسایه‬ ‫حالت‬ ‫است.وقتی‬ ‫حالت‬nt،‫شود‬ ‫می‬ ‫القا‬‫نق‬ ‫حالت‬ ‫خاصی‬ ‫شیوه‬ ‫به‬‫زمان‬ ‫در‬ ‫نظر‬ ‫مورد‬ ‫طه‬0n+t".‫شود‬ ‫می‬ ‫ست‬
‫ماشین‬ ‫یک‬ ‫شد‬ ‫استفاده‬ ‫نیومن‬ ‫فون‬ ‫توسط‬ ‫که‬ ‫را‬ ‫سلولی‬ ‫آتوماتای‬93‫که‬ ‫دهد‬ ‫می‬ ‫توضیح‬ ‫را‬ ‫حالته‬‫کار‬ ‫این‬‫از‬ ‫قبل‬0399‫شده‬ ‫کامل‬
.‫نشد‬ ‫منتشر‬ ‫حیاتش‬ ‫زمان‬ ‫در‬ ‫و‬ ‫بود‬
‫سال‬ ‫در‬0391‫.در‬ ‫کرد‬ ‫ارائه‬ ‫زندگی‬ ‫نام‬ ‫به‬ ‫دوبعدی‬ )‫بازی‬ ‫نوع‬ ‫سلولی(یه‬ ‫ماشین‬ ‫یک‬ ‫کانوی‬‫یا‬ ‫اند‬ ‫زنده‬ ‫یا‬ ‫ها‬ ‫سلول‬ ،‫زندگی‬
‫اش‬ ‫همسایه‬ ‫سه‬ ‫یا‬ ‫دو‬ ‫با‬ ‫زنده‬ ‫سلول‬ ‫یک‬ ‫و‬ ‫شود‬ ‫می‬ ‫زنده‬ ‫اش‬ ‫زنده‬ ‫همسایه‬ ‫سه‬ ‫با‬ ‫دقیقا‬ ‫مرده‬ ‫سلول‬ ‫یک‬ : ‫از‬ ‫است‬ ‫عبارت‬ ‫قانون‬ ، ‫مرده‬
‫م‬ ‫تمام‬ ‫دهند؛در‬ ‫می‬ ‫حیات‬ ‫ادامه‬‫ساده‬ ‫تنهایی).قوانین‬ ‫یا‬ ‫حد‬ ‫از‬ ‫بیش‬ ‫(ازدحام‬ ‫ماند‬ ‫می‬ ‫باقی‬ ‫مرده‬ ‫یا‬ ‫میرد‬ ‫می‬ ‫سلول‬ ‫یک‬ ‫دیگر‬ ‫وارد‬
‫کند‬ ‫می‬ ‫تداعی‬ ‫را‬ ‫بودن‬ ‫زنده‬ ‫که‬ ‫کند‬ ‫می‬ ‫ایجاد‬ ‫را‬ ‫زیبایی‬ ‫الگوهای‬ ‫بازی‬‫محاسبات‬ ‫یک‬ ‫زندگی‬ ‫بازی‬ ‫قوانین‬ ‫کرد‬ ‫اثبات‬ ‫بعدا‬ ‫.کانوی‬
.‫است‬ ‫گیر‬ ‫عالم‬
‫قرن‬ ‫اواخر‬ ‫در‬0391‫کر‬ ‫پیشنهاد‬ ‫فردریک‬ ،‫کنیم‬ ‫می‬ ‫زندگی‬ ‫آن‬ ‫در‬ ‫ما‬ ‫که‬ ‫را‬ ‫جهانی‬ ‫د‬‫یک‬‫عقیده‬ .‫است‬ ‫بزرگ‬ ‫سلولی‬ ‫آتوماتای‬
.‫دارند‬ ‫اقامت‬ ‫سلولی‬ ‫آتوماتای‬ ‫در‬ ‫که‬ ‫هستند‬ ‫اطالعاتی‬ ‫های‬ ‫بسته‬ ‫فیزیکی‬ ‫مقادیر‬ ‫همه‬ ‫که‬ ‫بود‬ ‫این‬ ‫فردریک‬
‫اوایل‬ ‫در‬ ‫س.ولفرام‬0391‫آتوم‬ ‫ی‬ ‫درباره‬ ‫پژوهش‬ ‫یکسری‬ ‫از‬ ‫بعد‬ .‫کرد‬ ‫وارد‬ ‫را‬ ‫سلولی‬ ‫آتوماتای‬ ‫فیلد‬، ‫بعدی‬ ‫یک‬ ‫سلولی‬ ‫اتای‬
‫گرفت‬ ‫تصمیم‬‫سال‬ ‫کرد.در‬ ‫سلولی‬ ‫آتوماتای‬ ‫درباره‬ ‫خصوصی‬ ‫بررسی‬ ‫یک‬ ‫به‬ ‫شروع‬ ‫و‬ ‫کند‬ ‫گیری‬ ‫کناره‬ ‫نظراتش‬ ‫ارائه‬ ‫از‬9119
‫کتابی‬ ‫در‬ ‫ولفرام‬ ،‫سال‬ ‫پانزده‬ ‫از‬ ‫بعد‬"‫جدید‬ ‫علم‬ ‫نوع‬ ‫"یک‬ ‫نام‬ ‫با‬‫کرد‬ ‫منتشر‬ ‫را‬ ‫خودش‬ ‫کار‬.‫شد‬ ‫برانگیز‬ ‫بحث‬ ‫بسیار‬ ‫که‬
‫برای‬ ‫جالبی‬ ‫حقایق‬ ‫او‬‫آتوماتای‬ ‫و‬ ‫کوانتومی‬ ‫محاسبات‬ ‫در‬ ‫که‬ ‫مارگوس‬ ‫نورمن‬ ‫و‬ ‫توفولی‬ ‫توماس‬ ،‫بنت‬ ‫چارلز‬ ‫(مثل‬ ‫پیشرو‬ ‫دانشمندان‬
.‫گذاشت‬ ‫بجای‬ )‫بودند‬ ‫فعال‬ ‫سلولی‬
‫های‬ ‫سیستم‬ ،‫تصویر‬ ‫تولید‬ ‫و‬ ‫پردازش‬ ،‫مصنوعی‬ ‫زندگی‬ ،‫موازی‬ ‫محاسبات‬ : ‫باشد‬ ‫می‬ ‫زیر‬ ‫موارد‬ ‫در‬ ‫سلولی‬ ‫آتوماتای‬ ‫کاربردهای‬
،‫شناسی‬ ‫زیست‬ ‫کردن‬ ‫مدل‬.‫هنر‬ ‫و‬ ‫گرافیک‬ ،‫افزار‬ ‫سخت‬ ‫و‬ ‫الگوریتم‬ ‫طراحی‬ ،‫ها‬ ‫آشوب‬ ،‫فیزیکی‬ ‫و‬ ‫شیمیایی‬ ‫های‬ ‫سازی‬ ‫شبیه‬
‫بندی‬ ‫طبقه‬ ‫و‬ ‫تعریف‬

2
( ‫سلولی‬ ‫آتوماتای‬ ‫یک‬CA،‫شوند‬ ‫می‬ ‫نامیده‬ ‫ها‬ ‫سلول‬ ‫که‬ ‫هم‬ ‫به‬ ‫شبیه‬ ‫متناهی‬ ‫آتوماتاهای‬ ‫از‬ ‫نامتناهی‬ ‫منظم‬ ‫گسسته‬ ‫شبکه‬ ‫یک‬ ،)‫می‬
‫زمانی‬ ‫فواصل‬ ‫در‬ ‫کدام‬ ‫هر‬ ‫ها‬ ‫حالت‬ .‫باشد‬‫نامیده‬ ‫همسایه‬ ‫که‬ ‫محلی‬ ‫سلول‬ ‫متناهی‬ ‫تعدادی‬ ‫به‬ ‫سلول‬ ‫هر‬ ‫تکامل‬ .‫کند‬ ‫می‬ ‫تغییر‬ ‫گسسته‬
.‫دارد‬ ‫بستگی‬ ‫شوند‬ ‫می‬
‫به‬،‫تر‬ ‫فرموله‬ ‫طور‬‫چهارتایی‬ ‫یک‬ ‫سلولی‬ ‫آتوماتای‬(𝜹d,Q,N,‫که‬ ‫باشد‬ ‫می‬ )*Z∈d،‫آن‬ ‫ُعد‬‫ب‬Q‫های‬ ‫حالت‬ ‫از‬ ‫ای‬ ‫مجموعه‬
،‫ممکن‬dZ∈N‫و‬ ‫است‬ ‫متناهی‬ ‫های‬ ‫همسایه‬ ‫که‬Q| N|Q. ‫است‬ ‫محلی‬ ‫انتقال‬ ‫تابع‬
‫عناصر‬ ‫بوسیله‬ ‫و‬ ‫شده‬ ‫سازماندهی‬ ‫خط‬ ‫یک‬ ‫در‬ ‫آتوماتا‬ ‫های‬ ‫سلول‬Z‫همه‬ ‫از‬ ‫ای‬ ‫مجموعه‬ ‫سلول‬ ‫یک‬ ‫همسایه‬ .‫اند‬ ‫شده‬ ‫گذاری‬ ‫شاخص‬
‫تکاملش‬ ‫محلی‬ ‫بطور‬ ‫که‬ ‫هستند‬ ‫شبکه‬ ‫های‬ ‫سلول‬‫ا‬.‫شود‬ ‫می‬ ‫تعیین‬ ‫ن‬
‫این‬ ‫حال‬ ‫هر‬ ‫به‬ ،‫باشند‬ ‫نزدیک‬ ‫نیست‬ ‫نیاز‬ ‫سلول‬ ‫یک‬ ‫های‬ ‫همسایه‬ ‫عموما‬‫هر‬ ‫که‬ ‫دهد‬ ‫می‬ ‫نشان‬d_‫شبیه‬ ‫تواند‬ ‫می‬ ‫همسایه‬ ‫بعدی‬
‫بوسیله‬ ‫بشود‬ ‫سازی‬d_‫محلی‬ ‫هم‬ ‫نزدیکترین‬ ‫بعد‬.
‫شعاع‬،‫همسایگی‬‫بین‬ ‫فاصله‬‫دو‬ ‫و‬ ‫سلول‬‫ذکر‬ ‫قابل‬ ‫مسئله‬ ‫یک‬ ‫حالت‬ ‫تعداد‬ ‫مقابل‬ ‫در‬ ‫شعاع‬ ‫سازی‬ ‫بهینه‬ .‫است‬ ‫اش‬ ‫همسایه‬ ‫رترین‬
،‫محاسبات‬ ‫واقعی‬ ‫مدل‬ ‫یک‬ ‫برای‬ ‫که‬ ‫است‬ ‫توجه‬ ‫جالب‬ ‫این‬ .‫است‬‫نمایی‬ ‫هایشان‬ ‫حالت‬ ‫تعداد‬ ‫و‬ ‫شعاع‬ ‫نسبت‬ ‫که‬ ‫را‬ ‫سلولی‬ ‫آتوماتاهای‬
.‫کنیم‬ ‫نمی‬ ‫بررسی‬ ،‫است‬
(It is interesting to note that for a realistic model of computation we do not consider CAs whose ratio between the
radius and the number of states is exponential since in such a setting NP-complete problems can be solved in
polynomial time.)
‫در‬‫زیر‬: ‫آید‬ ‫می‬ ‫یک‬ ‫شعاع‬ ‫و‬ ‫حالت‬ ‫دو‬ ‫با‬ ‫بعدی‬ ‫یک‬ ‫ساده‬ ‫مثال‬ ‫یک‬
‫اولیه‬ ‫موقعیت‬ ‫با‬ ‫سازی‬ ‫شبیه‬ ‫تکه‬ ‫یک‬ ‫پایین‬ ‫در‬
{..11011..: ‫باشد‬ ‫می‬ }

3
‫برای‬ ‫کارآمدی‬ ‫نمایش‬ ‫ولفرام‬‫ارائه‬ ‫محلی‬ ‫توابع‬ ‫انتقال‬.)‫شود‬ ‫می‬ ‫نامیده‬ ‫قانون‬ ‫ها‬ ‫وقت‬ ‫بعضی‬ ‫(که‬ ‫کرد‬
: ‫دهیم‬ ‫می‬ ‫توضیح‬ ‫را‬ ‫بعدی‬ ‫یک‬ ‫مورد‬ ‫یک‬ ‫ادامه‬ ‫در‬
‫اینجا‬ ‫در‬9=99
.‫کنند‬ ‫می‬ ‫تعیین‬ ‫را‬ ‫شده‬ ‫داده‬ ‫سلول‬ ‫یک‬ ‫بعدی‬ ‫حالت‬ ‫که‬ ‫است‬ ‫حالت‬ ‫از‬ ‫مختلف‬ ‫ترکیب‬‫ازای‬ ‫به‬‫تابع‬ ‫ترکیب‬ ‫هر‬
.‫کند‬ ‫تولید‬ ‫یک‬ ‫یا‬ ‫صفر‬ ‫تواند‬ ‫می‬ )‫(قانون‬ ‫انتقال‬‫بنابراین‬99
‫بنابراین‬ .‫داریم‬ ‫شدنی‬ ‫قانون‬‫یک‬ ‫به‬ ‫بیتی‬ ‫هشت‬ ‫عدد‬ ‫یک‬ ‫دادن‬ ‫نسبت‬ ‫با‬
‫اش‬ ‫خروجی‬ ‫ترکیب‬ ‫در‬ ‫یعنی‬ ‫است‬ ‫صفر‬ ‫اگر‬ ‫که‬ ‫بطوری‬ ‫شود‬ ‫تنظیم‬ ‫و‬ ‫کرد‬ ‫مشخص‬ ‫را‬ ‫آن‬ ‫توان‬ ‫می‬ ‫قانون‬‫یک‬ ‫اگر‬ ‫و‬ ‫شده‬ ‫دیده‬ ‫صفر‬
.‫جاها‬ ‫دیگر‬ ،‫است‬
‫عدد‬ ‫باال‬ ‫در‬ ‫شده‬ ‫داده‬ ‫نشان‬ ‫قانون‬ ‫مثال‬ ‫برای‬10000001=092.‫است‬
‫اوایل‬ ‫در‬ ‫ولفرام‬0391‫را‬ ‫سلولی‬ ‫آتوماتاهای‬ ‫او‬ ‫و‬ ‫کند‬ ‫حاصل‬ ‫پیچیده‬ ‫رفتارهای‬ ‫تواند‬ ‫می‬ ‫ساده‬ ‫سلولی‬ ‫آتوماتای‬ ‫قوانین‬ ‫که‬ ‫برد‬ ‫پی‬
: ‫کرد‬ ‫بندی‬ ‫دسته‬ ‫اصلی‬ ‫دسته‬ ‫چهار‬ ‫به‬
‫کالس‬0‫به‬ ‫همیشه‬ ‫اولیه‬ ‫های‬ ‫موقعیت‬ ‫درباره‬ ‫"اطالعات‬ ‫که‬ ‫ساده‬ ‫رفتارهای‬ ‫بوسیله‬ ‫شده‬ ‫سازی‬ ‫مشخصه‬‫می‬ ‫فراموش‬ ‫سرعت‬
"‫شود‬‫قانون‬ .992‫تکامل‬ ‫یک‬ ‫زیر‬ ‫در‬ ،‫است‬ ‫کالس‬ ‫این‬ ‫از‬ ‫مثال‬ ‫یک‬‫اولیه‬ ‫تصادفی‬ ‫موقعیت‬ ‫شش‬ ‫بوسیله‬‫شده‬ ‫داده‬ ‫نشان‬:
‫کالس‬9‫اش‬ ‫اولیه‬ ‫های‬ ‫حالت‬ ‫بیشتر‬ ‫از‬ ‫و‬ ‫دارد‬ ‫متناوب‬ ‫مدارهای‬ ‫یا‬ ‫و‬ ‫است‬ ‫تر‬ ‫ثبات‬ ‫با‬ ‫اما‬ ‫است‬ ‫ساده‬ ‫نیز‬،‫آن‬ ‫از‬ ‫یکی‬ ‫با‬ ‫سریعتر‬
.‫شود‬ ‫می‬ ‫همگرا‬ ‫مدارها‬‫کالس‬ ‫یک‬ ‫در‬9‫می‬ ‫داشته‬ ‫نگه‬ ‫آخر‬ ‫پیکربندی‬ ‫در‬ ‫شرکت‬ ‫برای‬ ‫اولیه‬ ‫های‬ ‫حالت‬ ‫در‬ ‫اطالعات‬ ‫"بعضی‬
‫قانون‬ ."‫متمرکز‬ ‫شکل‬ ‫به‬ ‫همیشه‬ ‫لیکن‬ ‫شوند‬091: ‫است‬ ‫معمولی‬ ‫مثال‬ ‫یک‬

4
‫کالس‬9" ‫شده؛‬ ‫سازی‬ ‫مشخصه‬ ‫کردن‬ ‫ظاهر‬ ‫تصادفی‬ ‫بوسیله‬‫که‬ ‫بطوری‬ ‫را‬ ‫اطالعات‬ ‫تبادل‬ ‫از‬ ‫بزرگی‬ ‫محدوده‬ ‫دهد‬ ‫می‬ ‫نشان‬‫هر‬
‫دارد‬ ‫تبادل‬ ‫سیستم‬ ‫بخش‬ ‫دورترین‬ ‫با‬ ‫نهایت‬ ‫در‬ ‫تقریبا‬ ‫جا‬ ‫هر‬ ‫در‬ ‫شده‬ ‫ساخته‬ ‫تغییر‬ ‫گونه‬"‫که‬ ‫است‬ ‫آور‬ ‫تعجب‬ ‫تاحدودی‬ ‫این‬ .
‫قانون‬ ،‫هستند‬ ‫کالس‬ ‫این‬ ‫به‬ ‫ساده،وابسته‬ ‫سلولی‬ ‫آتوماتاهای‬91: ‫است‬ ‫آن‬ ‫مثال‬ ‫یک‬
‫کالس‬2‫کالس‬ ‫بین‬9‫و‬9‫ماند‬ ‫تغییر‬ ‫بدون‬ ‫ساختارهای‬ ‫کردن‬ ‫مخلوط‬ ‫با‬ ‫و‬ ‫است‬.‫شود‬ ‫می‬ ‫سازی‬ ‫مشخصه‬ ،‫خطی‬ ‫حرکت‬ ‫دارای‬ ‫یا‬ ‫ه‬
.‫باشد‬ ‫گیت‬ ‫یک‬ ‫بیت‬ ‫دو‬ ‫تواند‬ ‫می‬ ‫متقابل‬ ‫خطی‬ ‫ساختار‬ ‫دو‬ ‫بین‬ ‫برخورد‬‫اس‬ ‫کالس‬ ‫این‬ ‫به‬ ‫وابسته‬ ‫زندگی‬ ‫بازی‬‫شبیه‬ ‫همچنین‬ ‫ولفرام‬ .‫ت‬
‫کالس‬ ‫سلولی‬ ‫آتوماتای‬ ‫همه‬ ‫داد‬ ‫اقتران‬ ‫و‬ ‫کرد‬2.‫تورینگ‬ ‫ماشین‬ ‫به‬ ‫را‬
‫م‬ ‫ارزی‬ ‫هم‬ ‫اصل‬ ‫مدعی‬ ‫ولفرام‬ ،‫حقیقت‬ ‫در‬‫را‬ ‫نیستند‬ ‫ساده‬ ‫وضوح‬ ‫به‬ ‫که‬ ‫فرآیندهایی‬ ‫همه‬ ‫"تقریبا‬ : ‫کند‬ ‫می‬ ‫بیان‬ ‫که‬ ‫است‬ ‫حاسباتی‬
‫قانون‬ ‫ادامه‬ ‫داد".در‬ ‫نشان‬ ‫معادل‬ ‫عناصر‬ ‫های‬ ‫ویژگی‬ ‫محاسبات‬ ‫با‬ ‫توان‬ ‫می‬001: ‫است‬ ‫آمده‬
‫سلولی‬ ‫آتوماتای‬ ‫خواص‬
‫اصلی‬ ‫سلولی‬ ‫آتوماتای‬ ‫به‬ ‫برگردیم‬(d,Q,N,𝜹‫پیکربندی‬ ‫طریق‬ ‫از‬ ‫توان‬ ‫می‬ ،)‫شد‬ ‫فرموله‬ ،)‫شود‬ ‫می‬ ‫نامیده‬ ‫نیز‬ ‫کلی‬ ‫(حالت‬‫ن‬
‫که‬ ‫بطوری‬ ،‫داد‬ ‫توضیح‬ ‫را‬ ‫سلولی‬ ‫آتوماتای‬ ‫حالت‬QdZ:tc‫جایی‬‫که‬∈ 𝑸 𝒛 𝒅
tc.
‫سلولی‬ ‫آتوماتای‬ ‫تکامل‬‫تناوبی‬ ‫پیکربندی‬ ‫یک‬(0, t ≥tc).‫دارد‬
‫دهید‬ ‫اجازه‬‫تابع‬‫انتقال‬(1-ic)𝑮 𝜹=ic‫کنیم‬ ‫تعیین‬ ‫را‬‫؛‬𝑄 𝑧 𝑑
𝐺 𝛿 ∶ 𝑄 𝑧 𝑑
‫سلول‬ ‫هر‬ ‫برای‬ ‫و‬𝑍⃗: ‫داریم‬ ‫ما‬ ‫که‬
))dn+nd,…,zn1+n1(zt,…,c)da+nd, …,z11+n1(zt),cd,…,z1(zt(c𝜹(c)(z) =𝑮 𝜹
‫که‬ ‫جایی‬)𝒏 𝒏⃗⃗⃗⃗⃗,…,𝒏 𝟏⃗⃗⃗⃗⃗= (((dn,…nn1n),….,(da,…n11n)).‫کند‬ ‫می‬ ‫ارائه‬ ‫را‬ ‫همسایه‬
: ‫آمده‬ ‫پایین‬ ‫انتقال‬ ‫تابع‬ ‫دو‬ ‫در‬ ‫نیومن_همسایه‬ ‫فون‬ ‫مثال‬ ‫برای‬

5
,j))1(i+t),c1,j+i(t),(i,j),c1-(i,jt,j),c1-(it(c𝜹(c)(i,j) =. 𝑮 𝜹
‫برای‬ ‫حل‬ ‫راه‬ ‫نوع‬ ‫دو‬ ‫ادامه‬ ‫است.در‬ ‫ها‬ ‫سلول‬ ‫از‬ ‫نامتناهی‬ ‫آرایه‬ ‫یک‬ ‫به‬ ‫نیاز‬ ‫سلولی‬ ‫آتوماتای‬ ‫در‬ ‫کاربردی‬ ‫مشکل‬ ‫یک‬
: ‫است‬ ‫آمده‬ ‫مشکل‬ ‫این‬ ‫توقف‬
0.‫اینجا‬ : ‫متناهی‬ ‫پیکربندی‬c‫حالت‬ ‫یک‬ ‫برای‬ ‫که‬ ‫بطوری‬ ،‫شده‬ ‫پیکربندی‬eq‫خاموش‬ ‫متناهی‬‫معین‬ ‫و‬ ‫پشتیبانی‬ ،
، ‫متناهی‬}e)≠q𝒛⃗⃗/c(𝒛⃗⃗Supp(c) = {‫؛‬
9.‫پیکربندی‬ ‫در‬ : ‫ای‬ ‫دوره‬ ‫پیکربندی‬c‫یک‬ ،dZ∈𝒑⃗⃗⃗‫بطوری‬ ‫دارد‬ ‫وجود‬‫که‬dZ∀ 𝒑⃗⃗⃗ ∈),𝒛⃗⃗)=c(𝒑⃗⃗⃗+𝒛⃗⃗c(.
: ‫شود‬ ‫می‬ ‫نامیده‬ ‫سلولی‬ ‫آتوماتای‬ ‫یک‬
0-‫؛‬ ‫دارد‬ ‫خودش‬ ‫برای‬ ‫همسایه‬ ‫یک‬ ‫فقط‬ ‫سلول‬ ‫هر‬ ‫اگر‬ ،‫ناچیز‬
9-‫فاصله‬ ‫اگر‬ ،‫ساده‬‫؛‬ ‫باشد‬ ‫صحیح‬ ‫هددی‬ ‫هایش‬ ‫همسایه‬
9-.‫است‬ ‫هایش‬ ‫همسایه‬ ‫مرکزی‬ ‫عنصر‬ ‫سلول‬ ‫اگر‬ ،‫متقارن‬
،‫سلولی‬ ‫آتوماتای‬ ‫مهم‬ ‫زیرکالس‬ ‫یک‬‫آتوماتای‬ ‫زیرا‬ ،‫شده‬ ‫داده‬ ‫آموزش‬ ‫اولیه‬ ‫بطور‬ ‫که‬ ،‫است‬ ‫پذیر‬ ‫برگشت‬ ‫آتوماتای‬
.‫است‬ ‫شده‬ ‫استفاده‬ ‫پذیرند‬ ‫برگشت‬ ‫که‬ ‫ها‬ ‫پدیده‬ ‫خیلی‬ ‫کردن‬ ‫مدل‬ ‫برای‬ ‫سلولی‬
‫سلولی‬ ‫آتوماتای‬ ‫یک‬A‫دیگر‬ ‫سلولی‬ ‫آتوماتای‬ ‫یک‬ ‫اگر‬ ‫است‬ ‫پذیر‬ ‫برگشت‬ʹA‫که‬ ‫بطوری‬ ‫باشد‬2)=c1(c𝑮 𝜹‫و‬ ‫اگر‬
‫اگر‬ ‫فقط‬1)=c2(c𝑮 𝜹.‫که‬ ‫شود‬ ‫توجه‬‫همسایه‬ʹA‫از‬ ‫غیر‬A.‫باشد‬ ‫می‬
( ‫فرمولی‬ ‫نگاشت‬ ‫شبیه‬ ‫اگر‬ ‫است‬ ‫پذیر‬ ‫برگشت‬ ،‫سلولی‬ ‫آتوماتای‬ ‫که‬ ‫بردند‬ ‫پی‬ ‫ریچاردسون‬ ‫و‬ ‫هدلند‬bijective)‫خودش‬
.‫باشد‬
‫برای‬ ‫حقیقت‬ ‫در‬ .‫هستند‬ ‫نادر‬ ‫غیرناچیز‬ ‫پذیر‬ ‫برگشت‬ ‫سلولی‬ ‫آتوماتاهای‬d ≥ 9‫برگشت‬ ‫که‬ ‫نشده‬ ‫مشخص‬ ‫تکلیفش‬ ،
.‫نه‬ ‫یا‬ ‫است‬ ‫پذیر‬
( ‫توفولی‬ ‫حال‬ ‫هر‬ ‫به‬0399‫سلولی‬ ‫آتوماتای‬ ‫هر‬ ‫که‬ ‫برد‬ ‫پی‬ )k‫واقعی‬ ‫زمان‬ ‫در‬ ‫بشود‬ ‫سازی‬ ‫شبیه‬ ‫تواند‬ ‫می‬ ‫_بعدی‬
‫سلولی‬ ‫آتوماتای‬ ‫یک‬ ‫بوسیله‬k+0‫دیباکیو‬ ‫این‬ ‫بر‬ ‫عالوه‬ ،‫پذیر‬ ‫برگشت‬ ‫_بعدی‬‫سلولی‬ ‫آتوماتای‬ ‫یک‬ ‫به‬‫پذیر‬ ‫برگشت‬‫عالم‬
‫برد‬ ‫پی‬ ‫گیر‬.
: ‫منبع‬Quantum Cellular Automata by bassam Aoun & Mohmad Tarifi

�ݺ�ߣ

Classical cellular automata

Recommended

More Related Content

Similar to Classical cellular automata (20)

Classical cellular automata