اتوماتای سلولی زندگی-گونه

اتوماتای سلولی زندگی-گونه( انگلیسی:Life-like cellular automaton) به نوعی از اتوماتای سلولی می‌گویند که بسیار شبیه بازی زندگی کانوی[1] است، این نوع از اتوماتا معمولاً در فضای دکارتی دوبعدی بیان می‌شود و هر بعد از دو طرف تا بی‌نهایت ادامه دارد. به هر خانه از این فضا یک سلول گفته می‌شود.

در این نوع اتوماتا هر خانه دو حالت زنده یا مرده دارد و وضعیت هر خانه در هر مرحله از وضعیت همسایه‌هایش و خودش در مرحله قبل به صورت یکتا تعیین می‌شود.

قاعده همسایگی برای یک خانه مطابق قانون همسایگی مور تشخیص داده می‌شود که در این قاعده هر دو خانه که در حداقل یک نقطه اشتراک دارند با هم همسایه هستند، پس هر خانه در این نوع اتوماتا با ۸ خانه دیگر همسایه است.

نمایش قاعده

قاعده اتوماتای سلولی زندگی-گونه با استفاده از دو رشته تعیین می‌شود، قاعده برای همه خانه‌ها یکسان است و با توجه به این دو رشته مشخص می‌شود در مرحله بعد سلول وضعیتش چگونه تغییر می‌کند.

دو رشته به این صورت مشخص می‌شوند که رشته اول مربوط به سلول‌های زنده است، این رشته مشخص می‌کند در چه صورتی سول در مرحله بعد زنده می‌ماند و اگر هیچ‌کدام از شرایط رشته درست نباشد در مرحله بعد سلول می‌میرد. رشته دوم مشخص می‌کند برای یک سلول مرده در مرحله بعد تحت چه شرایطی سلول زنده می‌شود و اگر هیچ‌کدام از شرایط این رشته درست نباشد سلول در مرحله بعد نیز مرده باقی می‌ماند.

هر رشته به صورت یک دنباله از اعداد ۱ تا ۸ است که مشخص می‌کند چه تعداد از همسایه‌های زنده در این قاعده صدق می‌کنند، رقم‌هایی که در دنباله آمده‌اند در شرط دنباله صدق می‌کنند و سایر رقم‌ها در شرط دنباله صدق نمی‌کنند. معمولاً دو رشته را به صورت x/y نشان می‌دهند که x رشته قاعده برای سلول‌های زنده است و y رشته قاعده برای سلول‌های مرده‌است. مثلاً برای بازی زندگی کانوی قاعده‌ها به صورت ۲۳/۳ است.

مدل‌های دیگری نیز برای بیان قواعد اتوماتای سلولی زندگی-گونه بیان شده‌اند، از جمله ولفرم و پکارد[2] در سال ۱۹۸۵ روش کدینگ ولفرم را پیشنهاد دادند، که در این روش از نمایش تبدیل شده باینری به دهدهی برای وضعیت زندگی یک سلول با توجه به همسایه‌هایش تعریف شده‌بود.

در نوع دیگری از بیان قواعد مطابق روش گالی که از فرمت آر ال ای استفاده می‌کرد مشابه قواعد نوع اول دو رشته داریم که ابتدای رشته نوع اول حرف 'S' می‌آید که برای مشخص کردن قاعده زنده ماندن "Survival" است و ابتدای قاعده دوم حرف 'B' می‌آید که برای نشان دادن قاعده زنده شدن "Birth" یک سلول مرده‌است.

دسته‌بندی

اتوماتای سلولی زندگی-گونه را بر حسب الگوی رشدشان و منظم بودن یا نبودن به تعدادی دسته تقسیم می‌کنند:

  • مدل انفجاری
  • مدل گسترشی
  • مدل پایدار
  • مدل نامنظم

چند نمونه از قواعد معروف

بازی زندگی کانوی (۲۳/۳)

با توجه به نوع قواعد توصیف شده می‌توان دید تعداد قواعد ممکن برای اتوماتای سلولی زندگی-گونه بسیار زیاد است. در حالت کلی وضعیت هر خانه با توجه به زنده یا مرده بودنش و با توجه به امکان‌پذیر بودن یا نبودن هر یک از اعداد ۰ تا ۸ برای وضعیت زندگی‌اش در مرحله بعد از دو رشته که هر کدام حالت دارند پس در کل قاعده متفاوت می‌توانیم داشته باشیم. اما تعداد اندکی از این قواعد به صورت دقیق بررسی شده‌اند و برخی از این قواعد نام‌های خاص خودشان را دارند. معروف‌ترین این قواعد قاعده بازی زندگی کانوی است، قاعده این بازی به صورت ۲۳/۳ است و تعداد زیادی از الگوهای آن مورد بررسی قرار گرفته‌اند[3]. قواعد بسیار زیادی با الهام گرفتن از بازی زندگی کانوی به وجود آمده‌اند، تلاش عمده این قواعد برای ایجاد و پخش گلایدرهای منظم است.[4]

چند نمونه از قواعد معروف را در این بخش می‌آوریم:

  • قاعده تکرار کننده: قاعده این نوع از اتوماتای سلولی به صورت ۱۳۵۷/۱۳۵۷ است. در این قاعده هر الگو چند کپی از خودش را به وجود می‌آورد.[3]
  • قاعده ۲×۲: این قاعده کمی مشابه بازی زندگی کانوی است، اما الگوهای کاملاً متفاوتی ایجاد می‌کند. در این قاعده همه الگوها به صورت بلوک‌های ۲×۲ هستند.[3]
  • قاعده زندگی ۳۴: قاعده این نوع اتوماتا به صورت ۳۴/۳۴ است، این قاعده جزء اولین قواعدی است که برای جایگزینی به جای بازی زندگی کانوی در سال ۱۹۷۰ مورد بررسی قرار گرفت.[3]

این موراد فقط چند مورد از موارد متعدد بررسی شده از اتوماتای سلولی زندگی-گونه هستند. در سایت mirekw توصیف تعداد بیشتری از این اتوماتا آمده‌است.

ایده‌های دیگر برای ساختن اتوماتای سلولی زندگی-گونه

انواع متعددی از اتوماتای سلولی با الهام گرفتن از اتوماتای سلولی زندگی-گونه ساخته شده‌اند. در اغلب این اتوماتا تعداد همسایگی بیشتر از همسایگی مور است. در نوع دیگری از اتوماتای سلولی به جای فضای دوبعدی از فضای سه‌بعدی استفاده می‌کنند، همچنین انواعی از اتوماتای سلولی که سلول‌ها به صورت مثلث یا شش ضلعی هستند نیز طراحی شده‌اند.

منابع

  1. http://conwaylife.com
  2. Wolfram, Stephen; Packard, N. H. (1985), "Two-dimensional cellular automata", Journal of Statistical Physics, 38 (5–6): 901–946, doi:10.1007/BF01010423 Reprinted in Wolfram, Stephen (1994), Cellular Automata and Complexity, Westview Press, pp. 211–249, ISBN 978-0-201-62664-3.
  3. Wójtowicz, Mirek, Cellular Automaton Rules Lexicon — Family: Life, Mirek's Cellebration.
  4. http://www.ics.uci.edu/~eppstein/ca/
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.