آستانه ناشناختگی

یا چگونه کندترین برنامه رایانه‌ای محدودیت بنیان‌های ریاضی را آشکار می‌سازد؟

مقدمه

مدت زمان اجرای کد، پارامتر بسیار مهمی است و برنامه‌نویس هنگام کد زدن سعی می‌کند بهینه‌ترین کد را بنویسد. اما در سال 1962، ریاضی‌دان مجارستانی به نام تیبور رادو (Tibor Radó)، مساله متفاوتی مطرح کرد؛ چطور می‌توانیم برنامه‌ای بنویسیم که کامپیوتر اجرای آن را تا حد ممکن کِش بدهد. نه به این معنا که در چرخه‌ی بینهایت گیر کند بلکه حتما باید در نقطه‌ای پایان یابد ولی تا آنجا که می‌شود مراحل اجرای آن زیاد باشد. رادو اسم این برنامه‌ی غیربهینه ولی کاربردی را «بیوِرِ مشغول» (Busy Beaver) گذاشت.

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

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

بازی بیوِر مشغول

قبل از پرداختن به مسائل باز ریاضی، ببینیم نحوه‌ی کار این بازی چگونه است. بازیِ بیور مشغول که به اختصار به آن BB خواهیم گفت، مدل ساده شده‌ای از ماشین تورینگ است. ماشین تورینگ هم مدل ساده‌ای از یک رایانه است. نوار بی‌نهایت بلندی را تصور کنید که روی آن تعداد زیادی مربع وجود دارد. روی هر مربع می‌توان مقدار 0 یا 1 را نوشت (مقدار پیش‌فرض روی مربع 0 است). علاوه بر این نوار، کارت‌هایی وجود دارد مثلا به تعداد N عدد که دستورالعمل پردازش روی آن نوشته شده است. ماشین مرحله به مرحله اجرا می‌شود. در هر مرحله، ماشین، عددی را که روی مربعِ جاری نوشته شده، می‌خواند. سپس با توجه کارتِ جاری و عددی که خوانده شده، یا متوقف می‌شود، و یا روی مربع یک عدد نوشته و کارت بعدی را فعال می‌کند و سپس روی نوار به سمت چپ یا راست شیفت پیدا می‌کند. اگر تا اینجا متوجه نحوه‌ی کار ماشین نشدید، نهراسید! در ادامه با یک مثال ساده بازی بیور مشغول را با سه کارت انجام خواهیم داد که به آن BB-3 می‌گویند.

طبق تصویر بالا ما سه کارت داریم؛ کارت A، کارت B و کارت C. ماشین با خواندن کارت اول یا همان کارت A شروع به کار می‌کند. در هر کارت ستون سمت چپ نمایانگر مقداری است که ماشین از روی نوار در ابتدای هر مرحله می‌خواند که یکی از دو مقدار 1 یا 0 خواهد بود. در ستون سمت راست در هر سطر یک رشته‌ی سه کاراکتری وجود دارد. کاراکتر اول می‌گوید ماشین در مرحله بعد کدام کارت را بخواند. کاراکتر دوم می‌گوید ماشین روی نوار چه مقداری را بنویسد، و کاراکتر سوم می‌گوید ماشین در مرحله بعد به سمت چپ یا راست شیفت پیدا کند. در کارت C در ستون سمت راست برای مقدار 1، اولین کاراکتر H است، به این معنی که به هیچ کارتی نرو یا به عبارتی برنامه را متوقف کن.
توجه داشته باشید که این تنها یک کد از کدهای بسیاری است که می‌توان برای این سه کارت نوشت. به هر یک از این کدها یک ماشین تورینگ گفته می‌شود. بیشتر ماشین‌های نوشته شده وارد چرخه‌ی بینهایت می‌شوند که در بازی بیور مشغول مردود هستند یعنی تنها ماشین‌هایی قابل قبول هستند که بعد از اجرای چند مرحله متوقف شوند، ممکن است یک ماشین تورینگ چند میلیون مرحله داشته باشد ولی حتما باید در آخر کار متوقف شود. در مثال بالا ماشین بعد از 12 مرحله و نوشتن شش 1 روی نوار متوقف خواهد شد.
برنده‌ی بازی BB-N کسی است که ماشین تورینگِ N کارتی‌ای که طراحی کرده بیشترین مراحل را طی کند و در نهایت متوقف شود. تیبور رادو در هنگام معرفی بازی بیور مشغول اثبات کرد که سریِ BB(N) غیر قابل محاسبه است. مقدار این تابع سریعتر از هر تابع محاسبه‌پذیری رشد می‌کند. چهار مقدار اول این سری به دست آمده است ولی هیچ راهی برای یافتن همه مقادیر این سری وجود ندارد. تعداد حالت‌هایی که باید چک شود تا برنده‌ی بازی بیور مشغول با N مرحله مشخص شود، از فرمول زیر محاسبه می‌شود:

این فرمول نشان می‌دهد هر چه مقدار N افزایش یابد تعداد حالت‌هایی که باید چک شود (یا تعداد ماشین‌های تورینگ که باید نوشته شود) به شکلی سریعتر از نمایی افزایش خواهد یافت. به عنوان مثال در یک بازی بیور مشغول با دو کارت، تعداد 6561 ماشین تورینگ مختلف می‌توان نوشت. یکی از آنها تا 6 مرحله اجرا شده و بعد متوقف می‌شود. این ماشین که طولانی‌ترین مراحل اجرا را در بازی BB-2 به خود اختصاص داده برنده بازی است. عدد برنده در BB-3 مقدار 21 است که در سال 1965 توسط رادو و شن لین (Shen Lin) اثبات شد. عدد برنده در BB-4 مقدار 107 است که در سال 1983 توسط آلن بردی (Allan Brady) اثبات شد. پاسخ بازی‌های BB-5 به بعد را هیچکس نمی‌داند و هنوز کسی آنها را اثبات نکرده است.
از BB-5 به بعد گویی ارقام منفجر می‌شوند؛ محققان یک ماشین تورینگ 5 کارتی (یا 5 قانونی) را در سال 1989 شناسایی کرده‌اند که قبل از توقف 47.176.870 مرحله را اجرا می‌کند. هیچ کس نمی‌داند آیا این عدد، عدد برنده‌ی بازی BB-5 است یا خیر. اما تا اینجا می‌دانیم عدد برنده، بزرگتر یا مساوی آن است. تاکنون 43 ماشینِ دیگر برای بازی BB-5 منتشر شده که احتمالا هرگز متوقف نخواهند شد اما هیچ کس تاکنون نتوانسته عدم توقف آنها را ثابت کند.

مسائل باز ریاضی

دانشمند علوم کامپیوتر اسکات آرونسون (Scott Aaronson) در پژوهشی که اخیرا روی بازی بیور مشغول انجام داده به این نتیجه رسیده است که جستجو برای برنامه‌هایی با اجرای طولانی نظیر همین بازی می‌تواند مرزهای دانش ریاضی را به ما نشان دهد و حتی مشخص کند که چه چیزی شناختنی است. به گفته محققان، بازی بیور مشغول، معیار مشخصی برای ارزیابی سختی مسائلی همچون حدس گلدباخ و حدس ریمان فراهم می‌آورد. این بازی حتی ردی از نقاطی را که در آنجا بنیان منطقی ریاضی فرومی‌ریزد، آشکار می‌سازد. ریاضی‌دادن و منطق‌دان بزرگ کورت گودل تقریبا یک قرن پیش وجود چنین حوزه‌های کشف نشده‌ای در ریاضی را پیش‌بینی کرده بود. اما بازی بیور مشغول، مثل نقشه‌های باستانی که مرزهای جهان را نشان می‌داد سرزمین‌های ناشناخته‌ی ریاضی را بر روی خطی از اعداد نشان می‌دهد.

“روایت‌هایی از اقلیم آینده“

ماهنامه پیشران شماره آبان‌ماه 99

آستانه ناشناختگی

در حال حاضر برخی از ریاضی‌دانان در حال تحقیق و بررسی روی بازی بیور مشغول هستند تا بتوانند از آن به عنوان معیاری برای سنجش مسائل باز ریاضی استفاده کرده یا بفهمند اصولا چه چیزی از نظر ریاضی قابلیت شناسایی و اندازه‌گیری دارد. به عنوان مثال، حدس گلدباخ می‌پرسد که آیا هر عدد صحیح بزرگتر از 2 جمع دو عدد اول است؟ اثبات درستی یا نادرستی این حدس، واقعه‌ای تاریخی در نظریه اعداد خواهد بود، و کمک خواهد کرد تا ریاضی‌دانان توزیع اعداد اول را بهتر درک کنند.

در سال 2015، یک کاربر ناشناس به نام Code Golf Addict کدی را در گیت‌هاب منتشر کرد. این کد یک ماشین تورینگ 27 قانونی است که اگر و تنها اگر حدس گلدباخ نادرست باشد متوقف خواهد شد وگرنه تا بی‌نهایت اجرا می‌شود. این ماشین با شمارش تمام اعداد زوج بزرگتر از 4 کار می‌کند. به این صورت که تمام حاصل‌جمع‌های ممکن برای هر عدد را پیدا کرده و چک می‌کند آیا آن جفت عدد اول است یا خیر. به محض پیدا شدن جفت عدد اول، عدد زوج بعدی بررسی شده و روند قبلی تکرار می‌شود. اگر یک عدد صحیح زوج که توسط هیچ جفت عدد اولی قابل جمع نیست، یافت شود برنامه متوقف خواهد شد.

راه‌اندازی یک ماشین حساب برای حل حدس گلدباخ کافی نیست، چون ما نمی‌دانیم آیا پایانی بر این محاسبه وجود دارد یا خیر؟ اما بازی بیور مشغول مساله را کمی برای ما روشن می‌کند. اگر می‌دانستیم مقدار BB(27) چقدر است آنگاه می‌دانستیم حداکثر زمان مورد نیاز برای اینکه حدس گلدباخ به صورت خودکار حل شود، چقدر خواهد بود. چون می‌دانیم عدد BB(27) برابر است با حداکثر مراحلی که یک ماشین تورینگ با 27 قانون باید اجرا کند تا متوقف شود (اگر بتواند این کار را انجام دهد). اگر این عدد را بدانیم، می‌توانیم ماشین تورینگ را به تعداد همین عدد اجرا کنیم اگر ماشین در آن نقطه متوقف شد یعنی حدس گلدباخ نادرست بوده است. اما اگر تا آن مرحله رفت و متوقف نشد می‌توان با اطمینان گفت که از این به بعد نیز متوقف نخواهد شد؛ بنابراین حدس گلدباخ درست بوده است.

دشواری کار اینجاست که عدد BB(27) به طرز غیرقابل درکی بزرگ است، به طوریکه اجرای ماشینی که حدس گلدباخ را رد کند با آن تعداد مرحله، در عالم فیزیکی که ما زندگی می‌کنیم حتی در خیال هم ممکن نیست. با این وجود، این عدد بزرگِ غیرقابل درک همچنان تصویر دقیقی از عظمت چیزی است که به گفته آرونسون بیانگر دانش فعلی ما از نظریه‌ی اعداد است.

در سال 2016، آرونسون با همکاری دو نفر دیگر توانست یک ماشین تورینگ با 744 قانون شناسایی کند که اگر و تنها اگر حدس ریمان نادرست باشد، متوقف خواهد شد. حدس ریمان که مربوط به توزیع اعداد اول است و یکی از «مسائل هزاره»ای است که توسط موسسه ریاضی Clay انتخاب شده و برای حل آن یک میلیون دلار جایزه تعیین شده است. ماشین آرونسون هم راه‌حلی شبیه به ماشین گلدباخ دارد، یعنی بعد از طی BB(744) مرحله به صورت خودکار حدس ریمان را رد یا تایید خواهد کرد. این ماشین تا زمانی که نمونه رد کننده‌ی حدس را پیدا نکند شمارش را ادامه می‌دهد.

البته، مقدار BB(744) حتی از عدد عظیمی چون BB(27) نیز دست‌نیافتنی‌تر است. اما تلاش برای سنجش چیزی آسان‌تر نظیر BB(5)، به گفته‌ی آرونسون، می‌تواند مسائل جدیدی را نمایان کند که در نوع خود جالب هستند. به عنوان مثال، ریاضی‌دانی به نام پاسکال میشل (Pascal Michel) در سال 1993 نشان داد که نمایش تاریخچه‌ی اعدادِ اغلبِ ماشین‌های تورینگ با 5 قانون، رفتاری بسیار شبیه به عملکرد توصیف شده در حدس کولاتز دارند. حدس کولاتز که یکی دیگر از مسائل باز در نظریه‌ی اعداد است می‌گوید شما می‌توانید از هر عدد صحیحِ مثبت شروع کرده و دو کار را انجام دهید: 1- اگر عدد زوج است آن را بر 2 تقسیم کن. 2- اگر فرد است، آن را سه برابر کرده و یکی به آن اضافه کن. حدس این است که این فرایند در نهایت به عدد 1 ختم می‌شود.

اخیرا، آرونسون از معیار جدید نشأت گرفته از بازی بیور مشغول، برای اندازه‌گیری چیزی که او آن را «آستانه ناشناختگی» برای کل سیستم ریاضیات می‌نامد، بهره برده است. نظریه‌ی معروفِ ناتمامیت گودل در سال 1931 ثابت کرد که هر مجموعه از اصول موضوعه‌ی اساسی که بتواند به عنوان پایه‌ی احتمالیِ منطقی برای ریاضیات باشد، محکوم به یکی از این دو سرنوشت است: یا اصول موضوعه ناسازگار هستند و منجر به وقوع تناقض می‌شوند (مانند اثبات 1 = 0)، یا ناکامل هستند و نمی‌توانند تعدادی از گزاره‌های صحیح را درباره‌ی اعداد ثابت کنند (مانند ثابت کردن 2+2=4). نظریه‌ی مجموعه‌های زرملو-فرانکل که به عنوان پشتیبانِ سیستم اصلِ موضوعه‌ی تقریبا تمام ریاضیات جدید محسوب می‌شود هم مرزهای گودلی خاص خود را دارد، و آرونسون می‌خواست از بازی بیور مشغول برای تعیین مکان آن مرزها بهره ببرد.

در سال 2016، او و دانشجوی تحصیلات تکمیلی خود آدام یدیدیا (Adam Yedidia) یک ماشین تورینگ با 7910 قانون را طراحی کردند که اگر و تنها اگر نظریه مجموعه‌های زرملو-فرانکل ناسازگار باشد متوقف خواهد شد. به عبارتی BB(7910) محاسبه‌ای است که در چارچوب اصول موضوعه‌ی نظریه‌ی مجموعه‌های زرملو-فرانکل قرار نمی‌گیرد. برای اینکه ثابت کنیم BB(7910) یک عدد را به جای دیگری نشان نمی‌دهد، باید راه دیگری پیدا کنیم چون اصول موضوعه‌ی ذکر شده در اینجا کاربرد ندارد، درست مثل اینکه نتوان ثابت کرد 2+2 برابر با 4 است یا 5.

متعاقبا دانشمند دیگری به نام استفان اوریر (Stefan O’Rear) ماشین تورینگ دیگری با 748 قانون ابداع کرد که در صورت ناسازگار بودن اصول موضوعه‌ی زرملو-فرانکل، متوقف خواهد شد، در حقیقت او مرزهای آستانه ناشناختگی را از BB(7910) به BB(748) محدودتر کرد. هاروی فریدمن (Harvey Friedman)، منطق‌دان و استاد برجسته‌ی دانشگاه ایالتی اوهایو معتقد است این موضوع که تعداد قوانینِ ماشینِ تورینگ در حد دیوانه‌کننده‌ای بزرگ نیست، خود یک پیشرفت چشمگیر است. از نظر او تعداد قوانین را می‌توان تا 50 کاهش داد، به عبارتی مرزها را می‌توان حتی محدودتر کرد. آرونسون گمان می‌کند که آستانه‌ی واقعی حتی ممکن است به نزدیکیِ BB(20) برسد.

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

نویسنده: مجتبی یکتا؛ برنامه‌نویس ارشد
ماهنامه پیشران (آینده‌پژوهی کسب‌وکار)/‌آبان‌ماه 99