نمایش مبدأ برای دورهمی طرح و حل مساله ریاضی/بازی زندگی کانوی

راوی: ''فرحان معرفت''

راجع به این موضوع در '''دو جلسه''' صحبت شد: سه‌شنبه، '''۲۷ شهریور ۱۴۰۳''' و '''یکشنبه، ۱ مهر ۱۴۰۳'''

==گزارشی از مطالب کلاس==
===بازی زندگی کانوی===
در جلسات مربوطه، ابتدا به چیستی بازی زندگی ''(Life)'' که توسط '''John Conway''' جبریست نامدار قرن اخیر طراحی شده است، پرداخته شد.
==معرفی بازی==
بازی زندگی کانوی، یک اتوماتای سلولی است(در مورد اتوماتاهای سلولی در بخش مطالعه‌ی بیشتر منبع مطالعاتی ذکر شده است) که توسط ریاضیدان بریتانیایی جان هورتون کانوی در سال ۱۹۷۰ طراحی شده است. این بازی معروف ترین مثال شناخته‌شده از یک اتوماتای سلولی است.

این بازی در واقع یک بازی بدون بازیکن است، به این معنا که تکامل آن توسط وضعیت اولیه‌اش تعیین می‌شود و نیازی به دریافت ورودی از بازیکن انسانی ندارد. عنصر انسانی صرفا در ایجاد یک پیکربندی اولیه نقش دارد و چگونگی تکامل بازی مستقل از بازیکن است.

الگوی اولیه به عنوان "بذر" سیستم شناخته می‌شود. نسل اول با اعمال '''هم‌زمان''' قوانین بازی (که در ادامه آمده است) به هر سلول در بذر ایجاد می‌شود — تولدها و مرگ‌ها به‌طور هم‌زمان اتفاق می‌افتند و لحظه‌ی گسسته‌ای که این اتفاق می‌افتد را معمولا یک ''"تیک"'' در سیستم می‌گویند. (به عبارت دیگر، هر نسل تابع خالصی از نسل قبلی است.) قوانین به‌طور مکرر اعمال می‌شوند تا نسل‌های بعدی ایجاد شوند.

این بازی در یک مشبکه ۲ بعدی نامتناهی پیاده می‌شود که وضعیت هر شبکه‌ی آن در یکی از دو حالت ممکن ''زنده'' یا ''مرده'' قرار دارد. بازی زندگی دارای چهار قانون اصلی است که نحوه تعامل سلول‌ها را مشخص می‌کند:
=== قوانین بازی ===
# '''تنهایی:''' اگر یک سلول زنده کمتر از دو همسایه زنده داشته باشد، می‌میرد.
# '''زنده ماندن:''' اگر یک سلول زنده دو یا سه همسایه زنده داشته باشد، زنده می‌ماند.
# '''ازدحام:''' اگر یک سلول زنده بیشتر از سه همسایه زنده داشته باشد، می‌میرد.
# '''تولید مثل:''' اگر یک سلول مرده دقیقاً سه همسایه زنده داشته باشد، زنده می‌شود.
== توصیف ریاضی بازی ==
بازی زندگی بر روی یک شبکه دو بعدی نامتناهی از سلول‌ها اجرا می‌شود. هر سلول در این شبکه دارای دو حالت است: زنده (<math>1</math>) و مرده (<math>0</math>). وضعیت بازی در زمان <math>t</math> به‌عنوان تابع <math>f_t: \mathbb{Z}^2 \to \{0, 1\}</math> تعریف می‌شود. تابع <math>f_t(x, y)</math> نشان‌دهنده وضعیت سلول در مختصات <math>(x, y)</math> در زمان <math>t</math> است.

تکامل وضعیت‌ها بر اساس قوانین زیر صورت می‌گیرد:<br>
۱- '''تعداد همسایگان:''' تعداد همسایگان زنده برای هر سلول <math>(x, y)</math> به‌صورت زیر محاسبه می‌شود:
<math>N(x, y) = (\sum _{i=-1}^{1} \sum _{j=-1}^{1} f_t(x+i, y+j)) - f_t(x, y)</math>
که در آن <math>N(x, y)</math> تعداد همسایگان زنده را برای سلول <math>(x, y)</math> محاسبه می‌کند.<br>
۲- '''تکامل:''' وضعیت سلول در زمان <math>t+1</math> به‌صورت زیر تعریف می‌شود:
<math>f_{t+1}(x, y) =
\begin{cases}
1 & \text{if } N(x, y) = 3 \\
f_t(x, y) & \text{if } N(x, y) = 2 \\
0 & \text{otherwise}
\end{cases}</math>

**این قوانین در ظاهر ساده که نحوه تکامل سلول‌ها را کنترل می‌کنند، نتایج پیچیده و جالبی را به بار می‌آورند. 

==چند مثال از الگوهای بازی زندگی==

برای مثال اجازه دهید تکامل چند نمونه از الگوهای بدوی مطرح شده در کلاس را به همراه مثال‌های بیشتر بررسی کنیم:<br>
(اشکال با شبیه‌ساز وبسایت https://playgameoflife.com/ رسم شده‌اند)

===الگوهایی که در یک مرحله ناپدید می‌شوند===

- '''سلول تنها'''

[[پرونده:Example11.png|بی‌قاب|چپ |150px]]
[[پرونده:Example12.png|بی‌قاب|وسط |150px ]]
- '''خط عمودی (افقی) به طول دو سلول'''
[[پرونده:Example21.png|بی‌قاب|حاشیه|چپ |150px]]
[[پرونده:Example22CGL.png|بی‌قاب|حاشیه|وسط |150px]]

- '''خط مورب به طول دو سلول'''
[[پرونده:Example31.png|بی‌قاب|حاشیه|چپ |150px]]
[[پرونده:Example32.png|بی‌قاب|حاشیه|وسط |150px]]
* همانطور که مشاهده می‌کنید، این اجسام اولیه از مثال‌های اجسام بازی زندگی با '''''طول عمر یک''''' هستند. 
===چند مثال دیگر از الگوهای اولیه===
- '''خط عمودی(افقی) به طول ۳'''
[[پرونده:Example41.png|بی‌قاب|حاشیه|چپ |150px]]
[[پرونده:Example42CGL.png|بی‌قاب|حاشیه|وسط |150px]]
*این الگو به پیمانه‌ی دو متناوب است، یعنی خطوط عمودی و افقی به طول ۳ تا ابد به همدیگر تبدیل می‌شوند.
- '''خط مورب به طول ۳'''
[[پرونده:Example71.png|بی‌قاب|حاشیه|چپ |150px]]
[[پرونده:Example72.png|بی‌قاب|حاشیه|وسط |150px]]
[[پرونده:Example73.png|بی‌قاب|حاشیه|چپ |150px]]<br><br><br><br><br><br>
*این الگو برای خط متناوب دلخواه از طول n نیز به همین منوال است با این تفاوت که طول عمر خط متناوب با طول n برابر  <math>\lfloor (n+1)/2 \rfloor</math> است.
<br>
===یک مثال از الگویی پیچیده‌تر===
- ''خط عمودی از طول ۴ سلول''
[[پرونده:Example61.png|بی‌قاب|حاشیه|وسط |200px]]
[[پرونده:Example62.png|بی‌قاب|حاشیه|وسط |200px]]
[[پرونده:Example63.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:Example64.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:Example65.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:Example66.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:Example67.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:Example68.png|بی‌قاب|حاشیه|وسط|200px]]
* مشاهده می‌شود که بعد از نسل ۸ام الگو به نسل ۷ و دومرتبه به نسل ۸ تبدیل و مکررا بین این دو دگرگون می‌شود.
=== الگوهای مشهور ===
از جمله الگوهای مشهور در بازی زندگی می‌توان به الگوی '''Glider''' و '''Gosper Glider Gun''' اشاره کرد. Glider یک الگوی متحرک است که می‌تواند در طول صفحه حرکت کند، در حالی که Gosper Glider Gun یک الگوی ایستا است که به تولید Glider های جدید می‌پردازد. این الگوها نشان‌دهنده نحوه تعامل سلول‌ها و تولید الگوهای پیچیده‌تر هستند.

-  '''الگوی Glider ساده:'''
[[پرونده:01.png|بی‌قاب|حاشیه|وسط|200px]]

- ''' الگوی Gosper Glider Gun: ''' 
[[پرونده:Gospers_glider_gun.gif|بی‌قاب|حاشیه|وسط|200px]]
==سوالات مطرح شده در کلاس==
===مثال‌هایی از الگوهای ثابت کدامند؟===
برخی الگوها ثابتند، یعنی از نسل اول تا ابد بدون هیچ تغییری باقی می‌مانند و این ویژگی به وضوح از قرارگیری مناسب سلول‌ها قابل درک است. یک مثال از چنین الگویی‌، الگوی ''مربع ۲ در ۲'' است. مثال های بیشتر شامل ''نان''، ''کندوی زنبور'' و ''قایق'' است:
[[پرونده:still1.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:still2.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:still3.png|بی‌قاب|حاشیه|وسط|200px]]
[[پرونده:still4.png|بی‌قاب|حاشیه|وسط|200px]]
===آیا موجود بی پدر وجود دارد؟===
این سوال مطرح شده در کلاس، دقیقا همان سوالی است که خود جان کانوی در سال ۱۹۷۲ با جایزه‌ای ۵۰ دلاری در مجله‌ی lifeline مطرح می‌کند:
** ''آیا الگوی پایداری وجود دارد که تنها پدرش خودش باشد (شاید همراه با برخی از سلول‌های منفصل محو شده در فاصله‌ای دور که شمارش نمی‌شوند)؟''

این سوال در حقیقت بیان می‌دارد که آیا الگویی وجود دارد که هیچ الگوی متمایزی را نتوان به عنوان نسل قبلی‌اش در نظر گرفت مگر خودش؟ البته این استثنا نیز وجود دارد که ممکن است خودش را به همراه تعدادی سلول منفصل در فاصله‌های دور در نظر بگیریم که نقشی در تکامل خود الگو ندارند.<br>

'''Ilkka Törmä''' و '''Ville Salo''' در ۱۳ ژانویه ۲۰۲۲ به این سوال پاسخ مثبت دادند.
آنها اینکار را با ساختن یک زمین الگوی ثابت مرکب از بلوک ها و مارها انجام دادند. به دو نمونه از چنین الگوها دقت کنید که یکی از این الگو‌ها دارای کمترین جمعیت و دیگری دارای کمترین شرط مرزبندی است:
[[پرونده:nopapa1.png|بی‌قاب|حاشیه|چپ|200px]]
[[پرونده:nopapa2.png|بی‌قاب|حاشیه|وسط|200px]] <br>
در سمت چپ یک الگوی ثابت غیرقابل ساخت ۲۶ × ۳۲ با جمعیت ۳۳۴(با حداقل مرزبندی) و درسمت راست یک الگوی غیرقابل ساخت ۳۴×۲۸ با جمعیت ۳۰۶ (با حداقل جمعیت) را مشاهده می‌کنید.

===آیا می‌توان رفتار زندگی کانوی را پیش‌بینی کرد؟===
در جلسه‌ی دوم کلاس در مورد قابل پیش بینی بودن یا نبودن یک الگو از روی بذرش بحث شد: <br> 
سوال کلیدی این است که آیا می‌توان برای هر الگو یک تابع <math>P: \mathbb{Z}^2 \to \{0, 1\}</math> تعریف کرد که وضعیت هر سلول را در زمان <math>t</math> بر اساس وضعیت اولیه آن پیش‌بینی کند. این سوال به‌عنوان '''مسئله پیش‌بینی''' شناخته می‌شود و هنوز به‌طور کامل حل نشده است.
=== غیرقابل تصمیم‌پذیری ===
بازی زندگی کانوی ارتباط تنگاتنگی با نظریه محاسبه و غیرقابل تصمیم‌پذیری دارد. در واقع، این بازی به‌عنوان یک مدل محاسباتی از سیستم‌های خودسازنده شناخته می‌شود و برخی از مسائل مرتبط با آن می‌توانند به مسائل غیرقابل حل در علوم کامپیوتر ارتباط پیدا کنند.

==== تعریف غیرقابل تصمیم‌پذیری ====
غیرقابل تصمیم‌پذیری به وضعیتی اطلاق می‌شود که در آن هیچ الگوریتمی نمی‌تواند به‌طور عمومی به سوالات مربوط به تصمیم‌گیری پاسخ دهد. به‌عبارت دیگر، برای برخی مسائل، هیچ روش محاسباتی وجود ندارد که بتواند به‌طور قطعی پاسخ صحیح را ارائه کند.

==== مسائل غیرقابل تصمیم‌پذیر در بازی زندگی ====
در بازی زندگی، یکی از سوالات کلیدی این است که آیا یک الگوی خاص در نهایت به حالت ثابتی خواهد رسید یا خیر. این سوال به‌عنوان '''مسئله توقف''' شناخته می‌شود و مشابه مسئله '''Halting''' در نظریه محاسبه است.

* '''مسئله Halting:''' 
این مسئله می‌پرسد که آیا برای یک برنامه مشخص و ورودی خاص، برنامه در نهایت متوقف می‌شود یا خیر. در بازی زندگی، این سوال به بررسی این موضوع می‌پردازد که آیا یک الگوی خاص به حالت ثابتی می‌رسد یا به‌طور مداوم در حال تغییر خواهد بود.

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

یکی از مهم‌ترین اجزا، "گلایدر" (Glider) بود. گلایدر یک الگوی متحرک است که می‌تواند به طور پیوسته در محیط حرکت کند. این الگو به کانوی این امکان را می‌دهد که اطلاعات را در طول زمان منتقل کند. گلایدرها به عنوان واحدهای اطلاعاتی عمل می‌کنند و می‌توانند با استفاده از تغییرات وضعیت سلول‌ها، اطلاعات را حمل کنند.

==== الگوی تفنگ گلایدر ====
کانوی همچنین از "تفنگ گلایدر" (Glider Gun) استفاده کرد که می‌تواند گلایدرها را به طور مداوم تولید کند. این الگو به عنوان یک منبع تولید گلایدرها عمل می‌کند و می‌تواند به عنوان یک "ورودی" برای ماشین تورینگ در نظر گرفته شود. تفنگ گلایدر با تولید مداوم گلایدرها، امکان پردازش اطلاعات را فراهم می‌کند و به ماشین اجازه می‌دهد که در هر مرحله از اجرای الگوریتم، اطلاعات جدیدی را تولید و پردازش کند.

==== الگوهای ایستا ====
علاوه بر گلایدرها، کانوی از الگوهای ایستا (Still Lifes) نیز استفاده کرد. این الگوها به عنوان "حافظه" برای ماشین تورینگ عمل می‌کنند. الگوهای ایستا، سلول‌هایی هستند که در طول زمان تغییر نمی‌کنند و به عنوان نقاط ذخیره‌سازی اطلاعات عمل می‌کنند. کانوی با استفاده از این الگوها توانست ساختارهای پیچیده‌تری ایجاد کند که می‌تواند اطلاعات را در طول زمان نگه‌داری کند.

==== کارکرد ماشین تورینگ ====
ماشین تورینگ طراحی‌شده توسط کانوی به گونه‌ای بود که می‌توانست هر الگوریتم قابل محاسبه‌ای را شبیه‌سازی کند. او با استفاده از ترکیب گلایدرها و الگوهای ایستا، یک سیستم محاسباتی طراحی کرد که می‌توانست به طور مؤثر اطلاعات را پردازش کند. برای مثال، با استفاده از گلایدرها، او توانست عملیات جمع و تفریق را شبیه‌سازی کند و در واقع، نشان داد که می‌توان با استفاده از این سیستم، محاسبات ریاضی را انجام داد.

===آیا می‌توان بازی لایف را در سه بعد پیاده سازی کرد؟===
این بحث نیز از بحث‌های نیمه تمام کلاس بود که در مورد آن بحث چندان زیادی نشد‌، ولی برای مطالعه‌ی بیشتر در بحث های تکمیلی توضیحات اولیه ولی غیرمقدماتی در مورد آن به همراه هایپرلینک برخی کلید واژه ها آورده شده است.
==بحث های تکمیلی==

===تاریخچه و پیدایش بازی===
کانوی به مسئله‌ای که در دهه ۱۹۴۰ توسط ریاضیدان معروف '''جان فون نیومن''' ارائه شده بود، علاقه‌مند بود. فون نیومن سعی داشت ماشینی فرضی پیدا کند که بتواند از خود کپی بسازد و با ارائه‌ی یک مدل ریاضی برای چنین ماشینی با قوانین بسیار پیچیده بر روی یک شبکه مستطیلی در انجام این امر موفق شد . انگیزه‌ی ابتدایی بازی زندگی تلاش کانوی برای ساده‌سازی ایده‌های فون نیومن بود.<br>

این بازی اولین بار در شماره اکتبر ۱۹۷۰ مجله ''Scientific American''، در ستون "بازی‌های ریاضی" مارتین گاردنر، تحت عنوان '' ترکیب‌های شگفت‌انگیز بازی جدید جان کانوی 'زندگی' '' به‌طور عمومی معرفی شد. از دیدگاه نظری، یک ویژگی بسیار جالب این بازی این است که قدرت یک ماشین تورینگ یونیورسال را دارد: به این معنا که هر چیزی که می‌تواند به‌طور الگوریتمی محاسبه شود، می‌تواند در بازی زندگی کانوی محاسبه شود. گاردنر نوشت:<br>
"این بازی، کانوی را بلافاصله مشهور کرد، اما همچنین درهای یک حوزه جدید از تحقیقات ریاضی، '''''حوزه اتوماتای سلولی''''' را باز کرد. به دلیل تشابه بازی زندگی با ظهور، سقوط و تغییرات یک جامعه از موجودات زنده، این بازی به یک کلاس رو به رشد از آنچه که 'بازی‌های شبیه‌سازی' نامیده می‌شود تعلق دارد (بازی‌هایی که شبیه فرآیندهای واقعی زندگی هستند)."<br>

از زمان انتشار آن، بازی زندگی توجه زیادی را به خود جلب کرده است زیرا الگوها به طرز شگفت‌انگیز و شوکه کننده‌ای تکامل می‌یابند. این بازی نمونه‌ای از خودسازمان‌دهی است. این بازی برای فیزیکدانان، زیست‌شناسان، اقتصاددانان، ریاضیدانان، فیلسوفان، دانشمندان تولیدی و دیگران جالب است که مشاهده کنند چگونه الگوهای پیچیده می‌توانند از اجرای قوانین بسیار ساده به وجود آیند.<br>

در زمان عرضه‌‌ی زندگی کانوی نسل جدیدی از مینی‌کامپیوترهای ارزان قیمت به بازار عرضه می‌شدند، که به محبوبیت بیشتر این بازی کمک کردند، زیرا که این بازی می‌توانست ساعت‌ها بر روی این کامپیوترها که در شب برای کار دیگری استفاده نمی‌شدند، اجرا شود. از این نظر، این بازی زمینه‌ساز محبوبیت فراکتال‌های تولید شده توسط کامپیوتر بود. برای بسیاری، زندگی تنها یک چالش برنامه‌نویسی بود؛ یک سرگرمی به صرف برای هدر دادن چرخه‌های سی پی یو. اما برای برخی، زندگی معانی فلسفی بیشتری داشت. این بازی در طول دهه ۱۹۷۰ و بعد از آن پیروان خاصی پیدا کرد؛<br>

کانوی قوانین خود را با دقت و پس از آزمایش‌های قابل توجه انتخاب کرد تا سه معیار را برآورده کند:
۱. نباید الگوی اولیه‌ای وجود داشته باشد که برای آن اثبات ساده‌ای وجود داشته باشد که جمعیت می‌تواند بدون محدودیت رشد کند.<br>
۲. باید الگوهای اولیه‌ای وجود داشته باشند که ظاهراً بدون محدودیت رشد کنند.<br>
۳. باید الگوهای اولیه‌ای ساده وجود داشته باشند که برای مدت قابل توجهی رشد و تغییر کنند قبل از اینکه به یکی از راه‌های زیر به پایان برسند:<br>
  * به‌طور کامل محو شوند (به دلیل ازدحام یا کمبود جمعیت)؛ یا<br>
  * به یک پیکربندی پایدار که بعد از آن تغییر نمی‌کند، مستقر شوند، یا وارد یک فاز نوسانی شوند که در آن یک دوره بی‌پایان از دو یا چند دوره را تکرار کنند.


=== مسئله پدربزرگ ===

** این مساله‌ دارای مفاهیم و کلیدواژه‌های غیر مقدماتی است ولی برای مطالعه‌ی روان‌تر و شفاف تر، برای برخی مفاهیم و کلید واژه ها منبع مطالعاتی ذکر شده است.

مسئله پدربزرگ نیز سوالی است که توسط جان کانوی در سال ۱۹۷۲ در نشریه Lifeline Volume 6 مطرح شد:

آیا الگویی وجود دارد که دارای الگوی پدر باشد اما پدربزرگ نداشته باشد؟
کانوی جایزه نقدی ۵۰ دلاری برای "نخستین شخصی که مسئله پدربزرگ را به هر طریقی حل کند" در نظر گرفته بود. اما مسئله الگوی بدون پدربزرگ تا ماه مه ۲۰۱۶ بدون پاسخ ماند، تا زمانی که '''mtve''' چنین الگویی را ارائه داد. این الگو در رقابت 
''Pattern of the Year'' سال ۲۰۱۶ در فروم‌های ConwayLife.com مقام سوم را پس از الگوهای [https://conwaylife.com/wiki/Copperhead Copperhead] و [https://conwaylife.com/wiki/Copperhead Caterloopillars] کسب کرد.
==== ساخت الگو ====

این الگو  با استفاده از الگوریتمی مشابه الگوریتمی که نیکولای بلچنکو برای کشف [https://oeis.org/A196447 A196447] به کار برده بود توسط '''SAT PicoSAT solver''' پیدا شد :

# سعی کنید سلول بعدی را روشن و خاموش کنید؛
# از اولین سطح باغ‌های عدن عبور کنید؛ (برای اطلاعات بیشتر در مورد باغ عدن در اوتوماتای سلولی و به طور خاص  قضیه‌ی باغ عدن که توسط ادوارد مور بیان و اثبات شده است و وجود باغ‌های عدن در بازی لایف را تضمین می کند می‌توانید به صفحه‌ی https://conwaylife.com/wiki/Garden_of_Eden مراجعه کنید)
# حداقل تعداد پدربزرگ‌ها را انتخاب کنید، به طوری که "حداقل تعداد" به معنای عدد دقیق نیست، بلکه فاصله مینیمال بین اولین و آخرین باشد.

پیکربندی نهایی دارای مجموع ۱۷۹۲۰ والد است، اما هیچ پدربزرگی ندارد.

==== اعتبار سنجی ====

کشف mtve توسط ماتیاس مرزنیچ با '''JLS''' تأیید شد که مسئله پدربزرگ را حل می‌کند، مراحل تایید به صورت زیر است:<br>
('''JavaLifeSearch''' (که به اختصار JLS نامیده می‌شود) ورژن مستقل از پلتفرمی از برنامه جستجوی  [https://conwaylife.com/wiki/Lifesrc ''lifesrc''] دیوید بل با زبان جاواست که برای یافتن [https://conwaylife.com/wiki/Spaceship oscillator] و [https://conwaylife.com/wiki/Spaceship spaceship] های جدید طراحی شده است.)

# جستجویی را برای یافتن تمام پیشینیان یک‌نسلی الگوی mtve اجرا کنید. سلول‌هایی که در تمام راه‌حل‌ها دارای جایگیری یکسان بودند را کپی کنید.
# تمام سلول‌های تنظیم نشده را با "X" علامت‌گذاری کنید، دوره را به ۱ افزایش دهید و الگو را به آینده به مدت یک نسل منتقل کنید. سلول‌های خارجی را در نسل ۰ به "X" تنظیم کنید و یک جستجوی دیگر را اجرا کنید که در نهایت نتیجه "جستجو به پایان رسید: ۰ راه‌حل پیدا شد" را می‌دهد.

'''الگوی ارائه شده توسط mtve (بهینه شده)'''

[[پرونده:Gpapalessmtve2.jpg|قاب|حاشیه|وسط |چینش|اندازه|پیوند=پیوند|جایگزین=متن جایگزین|الگوی ۲۲ در ۲۲ بدون پدربزرگ ارائه شده توسط mtve]]

==== سطوح بعدی مساله ====

الگوی "دارای پدر و پدربزرگ، اما بدون جد بزرگ" و الگوی "یک پدر، پدربزرگ و جد بزرگ، اما بدون جد بزرگ‌تر" نیز با استفاده از همین روش ساخته شده‌اند.<br>
[[پرونده:GGpapalessmtve.jpg|قاب|حاشیه|وسط |چینش|اندازه|پیوند=پیوند|جایگزین=متن جایگزین|الگوی دارای پدر و پدربزرگ ولی فاقد پدرپدربزرگ ارائه شده توسط mtve]]
[[پرونده:GGGpapalessmtve.jpg|قاب|حاشیه|وسط |چینش|اندازه|پیوند=پیوند|جایگزین=متن جایگزین|الگوی دارای پدر و پدربزرگ و پدرپدربزرگ ولی فاقد پدرپدرپدربزرگ ارائه شده توسط mtve]]
در تاریخ ۶ ژانویه ۲۰۲۲، ایلكا تورما و ویله سالو نسخه‌ای عمومی از مسئله پدربزرگ را حل کردند و اثبات کردند که برای هر عدد طبیعی <math>n</math>، الگویی وجود دارد که دارای پیشینیان <math>n</math> نسل قبل است اما فاقد پیشینیان <math>(n+1)</math> نسل قبل است. علاوه بر این، این الگو در یک جعبه با قطر <math>O(\sqrt{\log(n)})</math> قرار می‌گیرد.
 (این اثبات را در این فروم از وبسایت conwaylife که مختص به حدس های حل نشده است می توانید پیدا کنید، پست شامل اثبات مربوط به 6 ژانویه 2022 است، کافیست چند پست پایین تر اسکرول کنید :) https://conwaylife.com/forums/viewtopic.php?&p=139854#p139854)

===بازی زندگی در ۳ بعد===
یک اتوماتای سلولی سه‌بعدی در فضای سه‌بعدی عمل می‌کند. مشابه اتوماتای سلولی یک‌بعدی و دو‌بعدی، اتوماتای سه‌بعدی نیز ممکن است با تعاریف متفاوت از همسایگی عمل کند و همچنین می‌تواند کل‌نگر یا غیرکل‌نگر، ایزوتروپیک یا غیرایزوتروپیک باشد.

به‌طور معمول، فضای سه‌بعدی به شکل یک شبکه از سلول‌های مکعبی در نظر گرفته می‌شود و برای نسخه‌ی سه‌بعدی، در تعریف همسایگی Moore ، هر سلول در مرکز همسایگی ۳ × ۳ × ۳ سلول قرار دارد که این یعنی هر سلول ۲۶ سلول همسایه‌ دارد که با آن‌ها در تماس است. برای نسخه‌ی سه‌بعدی همسایگی فون نیومن، یک سلول ۶ همسایه دارد که با آن‌ها یک وجه مشترک دارد.

در سال ۱۹۸۷، کارتر بیس مقاله‌ای نوشت که در آن به تحلیل معنایی به تصویر کشیدن بازی زندگی در یک جهان سه‌بعدی با سلول‌های مکعبی پرداخت. در این جهان هر سلول دارای ۲۶ همسایه است.او در این مقاله به این بحث پرداخت که اگر قوانینی برای این جهان سه بعدی تدوین کنیم، این قوانین چگونه باید باشند تا منجر به رفتار مشابهی با بازی زندگی شوند. او دو معیار برای این مساله مطرح کرد:

* باید موجوداتی شبیه گلایدرها (در دنیای دو بعدی)، به‌طور طبیعی از [https://conwaylife.com/wiki/Soup سوپ‌ها] به وجود آیند.
* سوپ‌ها باید رشد محدودی  از خود نشان دهند.

اعمال قاعده [https://conwaylife.com/wiki/Conway%27s_Game_of_Life B3/S23] در فضای سه‌بعدی به تنهایی معیار ۲ را برآورده نمی‌کند. مشابه با قوانین B2 در دو بعد، داشتن تولد با ۴ همسایه یا کمتر منجر به گسترش با سرعت فوق العاده‌ای می‌شود.

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

به‌طور کلی، افزایش از ۸ همسایه دو بعدی به ۲۶ همسایه سه‌بعدی، تعداد قوانین ممکن برای جهان زندگی را بسیار بیشتر می‌کند.کارتر بیس چندین تئوری برای این مساله ارائه داد که منجر به تقلیل قوانین منتخب برای جهان سه بعدی شد. او دریافت که قاعده B6/S567 رفتار مشابهی با رفتار بازی زندگی تولید می‌کند.



==مطالعه بیش‌تر==
''منابع زیر برای مطالعه بیشتر درج شده‌اند'': <br><br>
https://playgameoflife.com/
(وبسایت رسمی بازی لایف همراه با شبیه ساز)<br>
https://conwaylife.com/wiki/
(وبسایت لایف‌ویکی شامل جامع‌ترین کاتالوگ الگوهای بازی لایف و بحث های جذاب در قالب تاپیک‌های روزانه)<br>
https://www.imj-prg.fr/~jean-paul.allouche/acs2001.pdf
(نوت های آشنایی با اتوماتای سلولی و بازی زندگی)<br>
https://conwaylife.com/wiki/Unique_father_problem
(مساله‌ی الگوی بی پدر)<br>
https://cs.brown.edu/courses/cs195v/projects/life/edwallac/index.html
(شبیه سازی و توضیحات در مورد نحوه‌ی گسترش بازی زندگی به فضای سه بعدی)<br>
http://www.cs.unibo.it/~babaoglu/courses/cas00-01/papers/Cellular_Automata/Turing-Machine-Life.pdf
(بازی زندگی و ماشین تورینگ)<br>
https://arxiv.org/abs/2410.22389
(تصمیم ناپذیری در بازی زندگی)<br>
https://journals.aps.org/pre/abstract/10.1103/PhysRevE.48.3345
(دینامیک غیرخطی بازی زندگی)<br>



[[رده:دورهمی طرح و حل مساله ریاضی]]