آیا تا به حال سعی کردهاید عدد بعدی در یک دنباله را حدس بزنید؟ این یکی را امتحان کنید: ۱، ۶، ۲۱، ۱۰۷، ۴۷,۱۷۶,۸۷۰… عدد بعدی چیست؟ اگر گیج شدهاید، تنها نیستید. این یک دنباله معمولی نیست؛ اینها پنج عدد اول «سگ آبی پرکار» (Busy Beaver) هستند و سفری به کرانههای مطلق محاسبات و ریاضیات را نشان میدهند.
این جستجو بخشی از یک رقابت شگفتانگیز به نام بازی سگ آبی پرکار است که توسط ریاضیدان، تیبور رادو، در سال ۱۹۶۲ ابداع شد. هدف آن به زبان ساده اما در عمل فوقالعاده دشوار است: برای تعداد مشخصی از قوانین (مثلاً ‘n’)، باید برنامه کامپیوتری سادهای (یک ماشین تورینگ) را پیدا کنید که طولانیترین زمان ممکن را اجرا شود و در نهایت متوقف گردد. تعداد گامهایی که این ماشین برمیدارد، عدد سگ آبی پرکار یا BB(n) نامیده میشود.
در حالی که اعداد BB(1) تا BB(4) دههها پیش پیدا شدند، مقدار BB(5) به تازگی در سال ۲۰۲۴ توسط یک جامعه آنلاین متعهد به نام «چالش سگ آبی پرکار» (Busy Beaver Challenge) مشخص شد. اما چالش واقعی و سرگیجهآور، BB(6) است. هیچکس مقدار دقیق آن را نمیداند، اما میدانیم که به شکلی غیرقابل تصور عظیم است.
چقدر عظیم؟ در سال ۲۰۲۲، محققان ثابت کردند که تعداد گامهایی که قهرمان BB(6) برمیدارد آنقدر بزرگ است که حتی اگر میتوانستید روی هر اتم در جهان شناختهشده یک رقم حک کنید، باز هم نمیتوانستید آن را بنویسید. قبل از اینکه حتی شروع به پیشرفت کنید، اتمهایتان تمام میشد.
اسکات آرونسون، دانشمند کامپیوتر در دانشگاه تگزاس، آستین، آن را اینگونه توصیف میکند: «بسیار فراتر از هر چیزی است که بتوانیم درک کنیم یا به آن دست یابیم.»
این جستجو در قلب یکی از عمیقترین پرسشهای علوم کامپیوتر قرار دارد: مسئله توقف (Halting Problem). در سال ۱۹۳۶، آلن تورینگ ثابت کرد که هیچ الگوریتم واحدی وجود ندارد که بتواند تعیین کند هر برنامه دادهشدهای در نهایت متوقف میشود یا برای همیشه اجرا خواهد شد. بازی سگ آبی پرکار یک رویارویی عملی و بیرحمانه با این محدودیت نظری است. برای یافتن BB(n)، باید ثابت کنید کدام ماشینها متوقف میشوند و کدام نه—وظیفهای که به طور کلی غیرممکن است.
اخیراً، شکار BB(6) وارد عصر جدیدی شده است. آنچه زمانی حوزه محققان فردی مانند شاون لیگوتسکی و پاول کروپیتز بود، به یک تلاش مشترک تبدیل شده است. رقابت در سال ۲۰۲۲ با اکتشافات پیدرپی این دو نفر شدت گرفت که حد پایین شناختهشده برای BB(6) را به قلمرو یک عملیات ریاضی به نام تتریشن (Tetration) کشاند. اگر توانرسانی تکرار عمل ضرب باشد (مانند ۱۰³)، تتریشن تکرار عمل توانرسانی است (به صورت 10↑↑3 نوشته میشود که برابر با ۱۰ به توان ۱۰ میلیارد است). ماشینهای قهرمان بیش از 10↑↑15 گام اجرا میشدند!
درست امسال، جامعه مشترک «چالش سگ آبی پرکار» شاهد بود که یک مشارکتکننده مرموز با نام مستعار «mxdys» این رکوردها را در هم شکست. در ماه ژوئن، mxdys یک قهرمان جدید پیدا کرد که زمان اجرای آن برجی از دهها به ارتفاع ۱۰ میلیون طبقه است (10↑↑10,000,000). تنها ۹ روز بعد، او رکورد خود را با ماشینی شکست که زمان اجرای آن در سطحی کاملاً جدید قرار دارد و به عملیاتی به نام پنتِیشن (Pentation) (تتریشن تکراری یا ↑↑↑) نیاز دارد.
قهرمان جدید بیش از 2↑↑↑5 گام اجرا میشود. برای درک بهتر، این عدد یک برج توانی از عدد ۲ را نشان میدهد که ارتفاع خود آن یک عدد غیرقابل تصور بزرگ است. خودِ این نمادگذاری دیگر در جهان هستی جا نمیشود.
چالش هنوز تمام نشده است. محققان اکنون با ماشینهایی مانند «Antihydra» دست و پنجه نرم میکنند که تقریباً به طور قطع هرگز متوقف نمیشود، اما اثبات آن به مسائل حلنشده ریاضی مانند حدس کولاتز گره خورده است. این سفر فقط برای یافتن اعداد بزرگ نیست؛ بلکه برای گسترش مرزهای دانش بشری، منطق و آنچه اساساً قابل محاسبه است، میباشد.
همانطور که یکی از محققان، راشلین، بیان کرد: «برای من، معتبرترین دلیل برای پرداختن به ریاضیات این است که سرگرمکننده است. این هنر است. همیشه کار جدیدی برای انجام دادن وجود خواهد داشت.»
منبع: Quanta Magazine