«بازی زندگی» ریاضی، الگوهای تکراری طولانی را نشان می‌دهد | مجله کوانتا

در سال 1969، جان کانوی، ریاضیدان بریتانیایی، مجموعه ای ساده از قوانین را برای ایجاد رفتار پیچیده ابداع کرد. بازی زندگی او که اغلب به آن زندگی ساده می گویند، روی شبکه مربعی بی نهایت از سلول ها آشکار می شود. هر سلول می تواند "زنده" یا "مرده" باشد. این شبکه طی یک سری چرخش (یا «نسل‌ها») تکامل می‌یابد که سرنوشت هر سلول توسط هشت سلول اطراف آن تعیین می‌شود. قوانین به شرح زیر است:

1. تولد: یک سلول مرده با دقیقاً سه همسایه زنده زنده می شود.
2. بقا: یک سلول زنده با دو یا سه همسایه زنده زنده می ماند.
3. مرگ: یک سلول زنده با کمتر از دو یا بیش از سه همسایه زنده می میرد.

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

سال بعد، او الگوی بسیار پیچیده تری به نام تپ اختر را پیدا کرد که بین سه حالت مختلف در نوسان است.

بلافاصله پس از کشف نوسانگرها، کاوشگران اولیه بازی به این فکر افتادند که آیا نوسانگرهای هر دوره وجود دارد یا خیر. بیل گاسپر، برنامه نویس و ریاضیدان کامپیوتر، که در طی چند دهه آینده به کشف 1 نوسانگر جدید جدید ادامه داد، گفت: «در ابتدا ما فقط دوره های 2، 3، 4، 15 و 17 را می دیدیم. نوسانگرهای دوره 15 (در زیر نشان داده شده است) اغلب در جستجوهای تصادفی به طور شگفت انگیزی ظاهر شدند.

سورپرایزهایی در کمین کسانی بود که مایل به یافتن آنها بودند. گاسپر گفت: «از ساعت ها و روزهای تماشا، دوره 5 غیرممکن به نظر می رسید. سپس در سال 1971، دو سال پس از اختراع بازی، یکی پیدا شد. شکار برای اسیلاتورهای جدید به تمرکز اصلی بازی تبدیل شد، تلاشی که با ظهور فناوری رایانه تقویت شد. حساب‌های جستجوهای مخفیانه انجام شده در رایانه‌های اداری به سنگ بنای فرهنگ عامه بازی تبدیل شده است. گاسپر گفت: «میزان زمان کامپیوتری که از مین‌فریم‌های شرکت‌ها و دانشگاه‌ها به سرقت رفته بود، خیره‌کننده بود.

در طول دهه 1970، ریاضیدانان و علاقه‌مندان دوره‌های کوتاه دیگر را پر کردند و تعداد کمی از دوره‌های طولانی‌تر را یافتند. در نهایت، ریاضیدانان روشی سیستماتیک برای ساخت نوسانگرهای دوره طولانی کشف کردند. اما یافتن نوسانگرهایی با پریودهای بین 15 تا 43 دشوار بود. گفت: «مردم سال‌ها در تلاش بوده‌اند تا حد وسط را پیدا کنند مایا کارپوویچ، دانشجوی کارشناسی ارشد در دانشگاه مریلند. پر کردن شکاف‌ها، محققان را مجبور به رویاپردازی تعداد زیادی از تکنیک‌های جدید کرد که مرزهای آنچه را که با اتوماتای ​​سلولی امکان‌پذیر می‌دانستند، همانطور که ریاضیدانان شبکه‌های در حال تکاملی مانند Life می‌نامند، جابجا می‌کنند.

اکنون کارپوویچ و شش نویسنده مشترک در الف پیش چاپ دسامبر که آنها دو دوره گمشده آخر را پیدا کرده اند: 19 و 41. با پر شدن این شکاف ها، زندگی اکنون به عنوان "همه دوره ای" شناخته می شود - یک عدد صحیح مثبت نام ببرید، و الگویی وجود دارد که پس از آن چندین مرحله خود را تکرار می کند.

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

نوسانگرهایی با دوره‌های کوتاه‌تر از 15 را می‌توان به صورت دستی یا با الگوریتم‌های ابتدایی یافت که نوسانگرها را در یک سلول جستجو می‌کنند. اما با بزرگ‌تر شدن دوره، پیچیدگی آن نیز افزایش می‌یابد، که باعث می‌شود جستجوهای brute-force بسیار کمتر مؤثر واقع شوند. ماتیاس مرزنیچ، یکی از نویسندگان مقاله جدید که اولین نوسانگر دوره 31 را در سال 2010 کشف کرد، گفت: "برای دوره های کوچک، می توانید مستقیماً جستجو کنید." اما واقعاً نمی توانید فراتر از آن بروید. شما نمی توانید فقط یک دوره را انتخاب کنید و آن را جستجو کنید." (مرزنیچ دکترای ریاضی خود را در سال 2021 از دانشگاه ایالتی اورگان دریافت کرد، اما در حال حاضر در یک مزرعه کار می کند.)

در سال 1996، دیوید باکینگهام، مشاور کامپیوتر آزاد کانادایی و علاقه‌مند به زندگی که از اواخر دهه 1970 در جستجوی الگوها بود، نشان داد که می‌توان نوسانگرهای دوره 61 و بالاتر را با ارسال یک الگو در اطراف یک مسیر بسته در یک حلقه بی‌پایان ساخت. . باکینگهام با کنترل طول حلقه - و مدت زمانی که الگو برای تکمیل یک سفر رفت و برگشت طول کشید - دریافت که می تواند این دوره را به اندازه دلخواه خود بزرگ کند. او گفت: «این شیمی بدون بوهای خنده دار یا ظروف شیشه ای شکسته است. مانند ساختن ترکیبات و سپس بررسی فعل و انفعالات بین آنها. این بدان معنی بود که در یک لحظه، او راهی برای ساخت نوسانگرهایی با دوره های دلخواه طولانی، تا زمانی که بیشتر از 61 باشد، ابداع کرده بود.

نتایج زیادی در اواسط دهه 1990 وجود داشت، زمانی که بسیاری از نوسانگرهای گمشده بین 15 تا 61 از طریق ترکیب خلاقانه نوسانگرهای شناخته شده کشف شدند که نام های رنگارنگی به آنها داده شده بود. غذاخوری‌ها با چراغ‌های راهنمایی ترکیب شدند، آتشفشان‌ها جرقه‌ها را بیرون می‌ریزند، و خورندگان گلایدر می‌خورند.

در آغاز قرن بیست و یکم، تنها دوازده دوره هنوز برجسته بودند. مرزنیچ گفت: «حل این مشکل بسیار ممکن به نظر می رسید. در سال 21، اکتشاف جدیدی به نام حلقه اسنارک، تکنیک باکینگهام در سال 2013 را بهبود بخشید و بریدگی بالای آن را که ساخت نوسانگرها آسان بود از 1996 به 61 کاهش داد. این تنها پنج دوره از دست رفته باقی ماند. یکی دیگر در سال 43 و دو مورد دیگر در سال 2019 کشف شد که تنها 2022 و 19 باقی مانده است - هر دوی اول. Merzenich گفت: "اعداد اول سخت تر هستند، زیرا نمی توانید از نوسانگرهای دوره کوچک برای ساخت آنها استفاده کنید."

میچل رایلی، محقق فوق دکتری در دانشگاه نیویورک ابوظبی و یکی دیگر از نویسندگان مقاله جدید، مدتهاست که شیفته نوعی نوسانگر به نام hassler بوده است. رایلی توضیح داد: "روش کار مزاحم‌ها این است که شما یک الگوی فعال در وسط و برخی چیزهای ثابت در بیرون دارید که با آن واکنش نشان می‌دهد." ماده پایدار، به نام کاتالیزور، وجود دارد تا الگوی فعال را به حالت اولیه خود برگرداند.

طراحی آنها سخت است. رایلی گفت: "همه این الگوها فوق العاده شکننده هستند." "اگر یک نقطه را در جای خود قرار دهید، معمولاً منفجر می شوند."

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

رایلی کاتالیزورهایی را که Barrister پیدا کرده بود به برنامه جستجوی دیگری که آنها را با الگوهای فعال جفت می کرد، تغذیه کرد. او گفت که این بیشتر به شکست منجر شد. این نسبتاً نادر است که یکی از این کاتالیزورها از تعامل جان سالم به در ببرد. هیچ تضمینی برای موفقیت وجود ندارد شما فقط به نوعی انگشتان خود را روی هم می گذارید و امیدوارید که به جکپات رسیده باشید. کمی شبیه قمار است.»

در نهایت شرط او نتیجه داد. پس از چند اشتباه نزدیک - و تغییر در کد که جستجو را برای شامل الگوهای متقارن گسترش داد - یک برهمکنش کاتالیزوری را پیدا کرد که می‌توانست نوسانگر دوره 19 را حفظ کند. رایلی گفت: «مردم انواع جستجوهای واقعاً پیچیده را با تعداد زیادی کاتالیزور و بسیاری از چیزهای فعال کمیاب در وسط امتحان می کردند، اما تنها چیزی که لازم بود یافتن این کاتالیزور بزرگ جدید بود.

آخرین دوره گمشده، 41 ساله، توسط نیکولو براون، یکی دیگر از نویسندگان، که هنوز در مقطع کارشناسی رشته ریاضی در دانشگاه کالیفرنیا، سانتا کروز است، پیدا شد. براون از گلایدرها به عنوان کاتالیزور استفاده کرد، ایده ای که اولین بار توسط Merzenich ارائه شد.

کارپوویچ گفت: «ما در 10 سال گذشته رفتارهای عمیقی را کشف کرده‌ایم. «همه یک هفته جشن می گیرند – و سپس به سراغ چیزهای دیگر می روند. بسیاری از مشکلات دیگر برای حل وجود دارد.» آیا نوسانگرهای یک دوره معین را می توان کوچکتر کرد؟ آیا نوسانگرهایی را می توان یافت که هر سلول در آن نوسان کند؟ آیا می توان اسلحه را با دوره های خاص ساخت؟ آیا می توان سفینه های فضایی را طوری ساخت که با سرعت خاصی حرکت کنند؟

همانطور که باکینگهام می گوید، "مثل این است که یک بچه در یک فروشگاه اسباب بازی بی نهایت باشید."